給定一個正整數陣列 a，您的任務是計算對i和j(where 0 ≤ i < j < a.length) 的數量，使得a[i]和a[j]在其二進制表示中具有相同數量的 1。
約束大小(a)<10^9
例子
input=[3,4,5,6,1,2]
ans=6
possible pairs=[(3,5)(3,6)(5,6)(4,1)(4,2)(1,2)]
我的索爾：
def numPairs(input):
count=0
for i in range(0,len(input)):
for j in range(i 1,len(input)):
if bin(input[i]).count('1')==bin(input[j]).count('1'):
count =1
return count
此解決方案給出了時間限制錯誤
我們可以像二和一樣在 1 個回圈中轉換這個解決方案嗎？
uj5u.com熱心網友回復：
from collections import Counter
def num_pairs(input_arr):
res = 0
counter = Counter()
for el in input_arr:
num_ones = bin(el).count("1")
res = counter[num_ones]
counter[num_ones] = 1
return res
如果我們考慮每個數字常量中的 1 的計數操作，則該解決方案在O(n)時間和O(log n)空間上運行。否則我們可以說它O(n log n)及時運行，因為我們需要log n操作來計算每個數字中的 1 的數量。
這確實是二和問題的變體，其中配對標準已更改為在數字的二進制表示中具有相同數量的 1。
您當前的解決方案是二次時間復雜度。您仍然可以通過保存其中的計數來進行一些小的優化，input[i]同時將其與以下所有input[j]s進行比較。
uj5u.com熱心網友回復：
bin() 函式回傳給定數字的二進制字串。count("1") 以二進制表示形式獲取 1 的數量，并從該串列中找到組合的數量。
這是解決方案
def numPairs(inputs):
sum=0
L = list(map(lambda x: bin(x).count("1"), inputs))
for i in range(max(L) 1):
c=L.count(i)
if c>1:
sum = c*(c-1)/2
return int(sum)
或者可以更瘋狂并制作單線解決方案。這與純 python 解決方案一樣有效。特別是空間方面，因為它不構造串列。時間復雜度為 O(n)。
from collections import Counter
from functools import reduce
def numPairs(inputs):
return int(reduce(lambda x,y: x y, map(lambda x: x*(x-1)/2, Counter(map(lambda x: bin(x).count("1"), inputs)).values())))
print(numPairs([3,4,5,6,1,2])) # prints 6
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/350516.html
下一篇：搜索字串自定義函式演算法