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

lintcode:落单的数 ii single number ii

admin 11月 13, 2020 0

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

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

solution

class :
    """
    @param: A: An integer array
    @return: An integer
    """
    def singleNumberII(self, A):
        
        A.sort()
        for x in range(2,len(A),3):
            if A[x] != A[x-2]:
                return A[x-2]
        return A[-1]

other

class :
    """
	@param A : An integer array
	@return : An integer
    """
    def singleNumberII(self, A):
        
        n = len(A)
        d = [0 for i in xrange(32)]
        for x in A:
            for j in xrange(32):
                if ( ((1 << j) & x) > 0):
                    d[j] += 1
        ans = 0
        for j in xrange(32):
            t = d[j] % 3
            if (t == 1):
                ans  = ans + (1 << j)
            elif (t != 0):
                return -1
        return ans