为什么我的python代码这么慢（leetcode）？ [英] Why is my python code so slow (leetcode)?

问题描述

给出一个整数数组，每个元素除
出现两次。找到一个。

Given an array of integers, every element appears twice except for one. Find that single one.

注意：
您的算法应该具有线性的运行时复杂度。您可以在不使用额外内存的情况下实现它吗？

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

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的问题，实际上是交流率最高的问题。但是，随着代码的发展，它告诉我超过了时间限制，因此无法接受。谁能分析我的代码，包括复杂性？非常感谢。

It's a question from leetcode and actually the one with highest AC rate. However, as my code goes, it tells me Time Limit Exceeded and could not been accepted. Could any one analyze my code including the complexity? Thank you so much.

Upadate：
谢谢大家，我将上一个从列表更改为集合，效果很好！

Upadate: Thank you all and I have changed the "prev" from a list to a set, which works nicely!

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)

但是我仍在寻找解决方案，不需要像问题所描述的那样多余的记忆。

However I am still looking for solutions that requires no extra memories as the question describes.

更新：
我

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，这样可以减少搜索的费用。

Actually I an kinda confused that does the slice like nums[:i+1] create a separate list every loop? So is the creation of list the most time consuming here? I used set instead of list so this may reduce the cost for searching.

推荐答案

@Peter的回答很出色：

@Peter's answer is brilliant:

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

这篇关于为什么我的python代码这么慢（leetcode）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！