为什么我的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的问题,实际上是AC率最高的问题.但是,正如我的代码所说,它告诉我时间限制已超出并且无法被接受.任何人都可以分析我的代码,包括复杂性吗？非常感谢.

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 [:i + 1]这样的切片会在每个循环中创建一个单独的列表吗？那么创建列表最耗时吗？我使用set而不是list,这样可以降低搜索成本.

Answer 1

@彼得的答案很棒:

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