Блог

Учитывая массив положительных целых чисел a, ваша задача состоит в том, чтобы подсчитать количество пар i и j (где 0 ≤ i < j < a.length ), таких что a[i] и a[j] имеют одинаковое количество 1 в их двоичных представлениях.

размер ограничения(a)

Пример

 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 цикл, как две суммы?

 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
 

Это решение выполняется во O(n) времени и O(log n) пространстве, если мы рассмотрим операцию подсчета единиц в каждой числовой константе. В противном случае мы можем сказать, что он выполняется O(n log n) вовремя, так как нам нужны log n операции для подсчета количества единиц в каждом числе.

Это действительно вариация задачи с двумя суммами, в которой критерии спаривания были изменены на одинаковое количество единиц в двоичном представлении числа.

Ваше текущее решение имеет квадратичную временную сложность. Вы все еще можете выполнить небольшую оптимизацию, сохранив количество единиц input[i] при сравнении со всеми следующими input[j] .

функция bin() возвращает двоичную строку с заданным числом. подсчитайте(«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