首页 > itarticle > lintcode:落单的数 single number

lintcode:落单的数 single number

admin 11月 13, 2020 0

给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。

样例
给出 [1,2,2,1,3,4,3]，返回 4

solution

class :
    """
    @param: A: An integer array
    @return: An integer
    """
    def singleNumber(self, A):
        
        from collections import Counter
        answer = Counter(A)
        for key in answer:
            if answer[key] == 1:
                return key
        return 0

提示 x^x = 0

other

class :
    """
   @param A : an integer array
   @return : a integer
   """
    def singleNumber(self, A):
        
        ans = 0;
        for x in A:
            ans = ans ^ x
        return ans

class :
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        A.sort()
        for i in range(1, len(A), 2):
            if A[i] != A[i-1]: # 与前一元素对比
                return A[i-1]
        return A[-1] # 要找的元素是最后一个元素