題目

給定一個(gè)長(zhǎng)度為偶數(shù)的整數(shù)數(shù)組 arr，只有對(duì) arr 進(jìn)行重組后可以滿足 “對(duì)于每個(gè) 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 時(shí)，返回 true；否則，返回 false。

示例 1：
輸入：arr = [3,1,3,6]
輸出：false
示例 2：
輸入：arr = [2,1,2,6]
輸出：false
示例 3：
輸入：arr = [4,-2,2,-4]
輸出：true
解釋：可以用 [-2,-4] 和 [2,4] 這兩組組成 [-2,-4,2,4] 或是 [2,4,-2,-4]
提示：
0 <= arr.length <= 3 * 10^4
arr.length 是偶數(shù)
-10^5 <= arr[i] <= 10 ^5
來(lái)源：力扣（LeetCode）

解題思路

??分析題目，可知我們需要將給定的數(shù)從新組合成符合條件的列表，其中下標(biāo)從0開(kāi)始每數(shù)兩個(gè)數(shù)，這兩個(gè)數(shù)要符合一定的規(guī)則，此規(guī)則就是后者是前者的兩倍，所以想要構(gòu)造這樣的數(shù)組，需要先對(duì)數(shù)組進(jìn)行排序，而對(duì)于負(fù)數(shù)而言則恰恰相反，同時(shí)需要考慮數(shù)組中可能存在重復(fù)的數(shù)字，所以我們需要用到字典來(lái)統(tǒng)計(jì)元素的頻率是否足夠分配成對(duì)。若從小到大來(lái)排的話，負(fù)數(shù)部分需要從大到小來(lái)排，對(duì)于任意一對(duì)緊挨著的數(shù)對(duì)應(yīng)符合的頻率規(guī)則為，后者較大數(shù)字的頻率要大于等于前者這樣才能存在一種可能，就是再后面的數(shù)與當(dāng)前對(duì)的后者匹配成對(duì)。

class Solution:def canReorderDoubled(self, arr: List[int]) -> bool:num=Counter(arr) #統(tǒng)計(jì)元素頻率L=list(num.items())L.sort()  #從小到大排序i=bisect.bisect([j[0] for j in L],0) #定位負(fù)數(shù)的范圍L=L[0:i][::-1]+L[i:] #負(fù)數(shù)排序for i in L:if num[i[0]]>0:try: #不存在成對(duì)的后者則不成立if num[i[0]*2]>0:  num[i[0]*2]-=num[i[0]] #試圖組合成前者頻率數(shù)量的對(duì)數(shù)num[i[0]]=0 #前者匹配完成if num[i[0]*2]<0:#后者較大數(shù)字的頻率要大于等于前者return Falseelse:return Falseexcept:return Falsereturn True

總結(jié)

以上是生活随笔為你收集整理的LeetCode中等题之二倍数对数组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。