计算二进制表示中具有相同数量的数字对

Question

给定一个正整数数组 a，您的任务是计算 i 和 j 对的数量（其中 0 ≤ i < j < a.length），使得 a[i] 和a[j] 在它们的二进制表示中有相同数量的 1。

constraint size(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 个循环中转换此解决方案？

Answer 1

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) space。否则我们可以说它在 O(n log n) 时间内运行，因为我们需要 log n 次操作来计算每个数字中的个数。

这确实是两个和问题的变体，其中配对标准已更改为在数字的二进制表示中具有相同数量的 1。

您当前的解决方案具有二次时间复杂度。您仍然可以通过在 input[i] 中保存 1 的计数，同时将其与以下所有 input[j]s.

进行比较来进行一些小的优化

Answer 2

bin() 函数 returns 给定数字的二进制 string。 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 解决方案一样有效。特别是 space-wise 因为它不构建列表。时间复杂度为 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

计算二进制表示中具有相同数量的数字对

Count pairs of numbers with equal number of ones in their binary representation

python

algorithm

bit-manipulation

list