首页 > 代码库 > Leetcode_num1_Single Number

Leetcode_num1_Single Number

好久没有做题啦,从今天开始刷Leetcode的题,希望坚持的时间能长一点。先从ac率最高的Single Number开始吧。

题目:

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?

刚开始的代码是介样的:

def singleNumber(A):
    rs=0
    for i in range(len(A)):
        if A[i] not in A[0:i]+A[i+1:]:
             rs=A[i]
    return A[i]

python中判断是否在数组的in 其实也是o(n)的复杂度,所以整体算法复杂度是o(n^2)

为了达到o(n)的复杂度,必然不能使用两两比较的方法,只能遍历一次数组,从整型位操作的角度出发,将数组中所有的数进行异或,相同的数异或得零。能AC的代码是介样的:

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        rs=0
        for i in A:
            rs=rs^i
        return rs
又长见识了,感动得流泪了

Leetcode_num1_Single Number