Python целые числа бесконечно велики.Они не станут отрицательными, если вы добавите больше битов, поэтому дополнение к двум может работать не так, как ожидалось.Вы можете управлять негативами по-разному.
def singleNumber(nums):
result = 0
sign = [1,-1][sum(int(n<0) for n in nums)%3]
for i in range(32):
counter = 0
for num in nums:
counter += (abs(num) >> i) & 1
result = result | ((counter % 3) << i)
return result * sign
Этот бинарный подход может быть оптимизирован и упрощен следующим образом:
def singleNumber(nums):
result = 0
for i in range(32):
counter = sum(1 for n in nums if (n>>i)&1)
if counter > 0: result |= (counter % 3) << i
return result - 2*(result&(1<<31))
Если вам нравятся один лайнер, вы можете реализовать его с помощью Redu () изfunctools:
result = reduce(lambda r,i:r|sum(1&(n>>i) for n in nums)%3<<i,range(32),sum(n<0 for n in nums)%3*(-1<<32))
Обратите внимание, что этот подход всегда будет делать 32 прохода через данные и будет ограничен числами в диапазоне -2 ^ 31 ... 2 ^ 31.Увеличение этого диапазона будет систематически увеличивать количество проходов по списку чисел (даже если список содержит только небольшие значения).Кроме того, поскольку вы не используете counter [i] вне цикла i, вам не нужен список для хранения счетчиков.
Вы можете использовать базу 3 вместо базы 2, используяочень похожий подход (который также отвечает в O (n) времени и O (1) пространстве):
def singleNumber(nums):
result = sign = 0
for num in nums:
if num<0 : sign += 1
base3 = 1
num = abs(num)
while num > 0 :
num,rest = divmod(num,3)
rest,base3 = rest*base3, 3*base3
if rest == 0 : continue
digit = result % base3
result = result - digit + (digit+rest)%base3
return result * (1-sign%3*2)
Преимущество этого подхода состоит в том, что он будет проходить список только один раз (таким образом, поддерживаяитераторы в качестве входных данных).Он не ограничивает диапазон значений и выполняет вложенный цикл while как можно меньшее количество раз (в соответствии с величиной каждого значения)
Способ, которым он работает, заключается в добавлении цифр независимо впредставление базы 3 и циклический результат (цифра за цифрой) без применения переноса.
Например: [16, 16, 32, 16]
Base10 Base 3 Base 3 digits result (cumulative)
------ ------ ------------- ------
16 121 0 | 1 | 2 | 1 121
16 121 0 | 1 | 2 | 1 212
32 2012 2 | 0 | 1 | 2 2221
16 121 0 | 1 | 2 | 1 2012
-------------
sum of digits % 3 2 | 0 | 1 | 2 ==> 32
Процессы цикла while num > 0цифры.Он будет работать не более log (V, 3) раз, где V - наибольшее абсолютное значение в списке чисел.Как таковой он похож на цикл for i in range(32) в решении base 2, за исключением того, что он всегда использует наименьший возможный диапазон.Для любого заданного шаблона значений число итераций цикла while будет меньше или равно константе, тем самым сохраняя сложность O (n) основного цикла.
Я провел несколько тестов производительностии на практике версия base3 только быстрее, чем подход base2, когда значения малы.Подход base3 всегда выполняет меньше итераций, но, когда значения большие, он проигрывает в общем времени выполнения из-за накладных расходов по модулю против побитовых операций.
Чтобы решение base2 всегда было быстрее, чем baseПри использовании подхода 3 ему необходимо оптимизировать свои итерации по битам путем обращения вложенности цикла (биты внутри чисел вместо цифр внутри битов):
def singleNumber(nums):
bits = [0]*len(bin(max(nums,key=abs)))
sign = 0
for num in nums:
if num<0 : sign += 1
num = abs(num)
bit = 0
while num > 0:
if num&1 : bits[bit] += 1
bit += 1
num >>= 1
result = sum(1<<bit for bit,count in enumerate(bits) if count%3)
return result * [1,-1][sign%3]
Теперь он будет превосходить базовый подход 3 каждый раз,Дополнительным преимуществом является то, что он больше не ограничен диапазоном значений и будет поддерживать итераторы в качестве входных данных.Обратите внимание, что размер массива битов можно рассматривать как константу, так что это также решение пространства O (1)
Но, если честно, если мы применим ту же оптимизацию к базе 3подход (т. е. с использованием списка 3 базовых «битов»), его производительность возвращается вперед для всех размеров значений:
def singleNumber(nums):
tribits = [0]*len(bin(max(nums,key=abs))) # enough base 2 -> enough 3
sign = 0
for num in nums:
if num<0 : sign += 1
num = abs(num)
base3 = 0
while num > 0:
digit = num%3
if digit: tribits[base3] += digit
base3 += 1
num //= 3
result = sum(count%3 * 3**base3 for base3,count in enumerate(tribits) if count%3)
return result * [1,-1][sign%3]
.
Счетчик из коллекций даст ожидаемый результат вO (n) время с одной строкой кода:
from collections import Counter
numbers = [1,0,1,0,1,0,99]
singleN = next(n for n,count in Counter(numbers).items() if count == 1)
Наборы также будут работать в O (n):
distinct = set()
multiple = [n for n in numbers if n in distinct or distinct.add(n)]
singleN = min(distinct.difference(multiple))
Эти два последних решения действительно используют aпеременный объем дополнительной памяти, который пропорционален размеру списка (т.е. не O (1) пробел).С другой стороны, они работают в 30 раз быстрее и будут поддерживать любой тип данных в списке.Они также поддерживают итераторы