Почему мой код python настолько медленный (leetcode)?

Question

Учитывая массив целых чисел, каждый элемент появляется дважды, за исключением . Найдите этот единственный.

Примечание: Ваш алгоритм должен иметь сложность линейного выполнения. Не могли бы вы реализовать его без использования дополнительной памяти?

class Solution: 
    # @param {integer[]} nums 
    # @return {integer} 
    def singleNumber(self, nums): 
     prev = [] 
     for i,j in enumerate(nums): 
      if j in prev: 
       nums[i] = -j 
      else: 
       prev.append(j) 
     return sum(nums) 

Это вопрос от leetcode и на самом деле один с самой высокой скоростью переменного тока. Однако, как мой код идет, он говорит мне, что Time Limit Exceeded и не может быть принят. Может ли кто-нибудь проанализировать мой код, включая сложность? Огромное спасибо.

Upadate: Спасибо всем, и я изменил «prev» из списка на набор, который работает красиво!

class Solution: 
    # @param {integer[]} nums 
    # @return {integer} 
    def singleNumber(self, nums): 
     prev = set([]) 
     for i,j in enumerate(nums): 
      if j in prev: 
       nums[i] = -j 
      else: 
       prev.add(j) 
     return sum(nums) 

Однако я все еще ищу решения, которые не требуют лишних воспоминаний, как описывает этот вопрос.

Обновление: Я использовал другой способ, пытаясь решить проблему, но снова получил время превышенное.

class Solution: 
    # @param {integer[]} nums 
    # @return {integer} 
    def singleNumber(self, nums): 
     for i,j in enumerate(nums): 
      if j in set(nums[:i+1]): 
       nums[i] = -j 
     return sum(nums) 

На самом деле я своего рода замешательстве, что делает срез как Nums [: я + 1] создать отдельный список каждый цикл? Итак, создание списка является самым трудоемким здесь? Я использовал набор вместо списка, поэтому это может снизить стоимость поиска.

Answer 1

@ ответ Петра является блестящим:

def singleNumber(nums): 
    unique = 0 
    for num in nums: 
     unique ^= num 
    return unique 

Answer 2

Xor - это путь. Xor двух одинаковых элементов равен 0 и, следовательно, все дубликаты будут исчезать, в результате чего неперечисленный элемент будет присутствовать в res.

x=[1,1,2,3,2,4,4,5,5] 
res=x[0] 
for i in xrange(1,len(x)): 
    res^=x[i] 

print res 

Answer 3

Вот альтернативный, функциональный способ написания XOR-решения.

from operator import xor 

def single_number(nums): 
    return reduce(xor, nums) 

В Python 3.x (который, по-видимому Leetcode не использует) вам необходимо импортировать функцию reduce из functools модуля.

Answer 4

Вы можете использовать Cython (я использовал его сейчас во второй раз, так что, может быть, есть еще улучшение возможно):

Создайте файл singleNumber.pyx с следующим содержанием:

def singleNumber(list nums, int nn): 
cdef int i, ii, np 
cdef list prev = [] 

for i in xrange(nn): 
    np = len(prev) 
    for ii in xrange(np): 
     if nums[i] == prev[ii]: 
      nums[i] = - prev[ii] 
     else: 
      prev.append(nums[i]) 
return sum(nums) 

Создать файл setup.py с следующее содержание:

from distutils.core import setup 
from Cython.Build import cythonize 

setup(
    ext_modules=cythonize('singleNumber.pyx'), 
) 

Собирать: python setup.py build_ext --inplace

import singleNumber as sn 
arr = [i + 1 for i in range(1000)] 
%timeit sn.singleNumber(arr,len(arr)) 

Результат: 100000 loops, best of 3: 15.4 µs per loop

Использование функции XOR дает мне: 10000 loops, best of 3: 82.1 µs per loop

EDIT:

Я получаю разные результаты, если я использую XOR решения по сравнению с исходной функции!

from operator import xor 

def singleNumber_xor(nums): 
    return reduce(xor, nums) 

arr = [i + 1 for i in range(10000)] 
singleNumber_xor(arr) 

дает мне: 10000

Оригинальная функция:

def singleNumber_orig(nums): 
    prev = set([]) 
    for i,j in enumerate(nums): 
     if j in prev: 
      nums[i] = -j 
     else: 
      prev.add(j) 
    return sum(nums) 

singleNumber_orig(arr) 

дает мне: 50005000