算法19-----（位运算）找出数组中出现只出现一次的数

系统管理员 2021-03-28 14:40 421阅读 0赞

## 题目： ##

前三题都可以用集合和来求。【sum(set(nums)）\*N-sum(nums)】

1、数组中别的数都出现2次，只有一个数出现1次，找出该数。

2、数组中别的数都出现3次，只有一个数出现1次，找出该数。

3、数组中别的数都出现N次，只有一个数出现1次，找出该数。

4、数组中别的数都出现2次，只有两个数只出现1次，找出这两个数。

5、数组中1到1000遍历（顺序打乱），有两个数缺失，求出这两个数。

##  解题： ##

### 1、（3）第1题相当于第3题N为偶数。解法思路：数组为nums，则数组中所有数异或，最后的值为所求。 ###

def findNum(nums):
    　　if not nums:
    　　　　return -1
    
        i=0
        res=0while i<len(nums):
            res^=nums[i]
        return res

### 2、（3）第2题相当于第3题N为奇数。解法思路：所有数的二进制位相加 mod 3 ，所有模3值不为0的位汇总的数即为所求。 ###

def findNum(nums):
        if not nums:
            return -1
        i=0
        res=0
        bitSum=[0]*4
        while i<4:
            j=0
            while j<len(nums):
                bitSum[i]+=(nums[j]>>i)&1
            res|=(bitSum[i]%3)<<i
            i+=1
        return res

更简单的解法：一个数用来表示出现一次的位，也就是说这个数的为1的位就表示这个位上面的数出现过了一次，比如0x10001，就表示bit\[0\]和bit\[4\]就是出现过了一次的位。然后再用一个数表示出现过了两次的位，再用一个数表示出现过了3次的位。只要这个位出现过了3次，我就把这个位拿清除掉，这样剩余的最后出现过一次的位的这个数就是我们要找的数了。

def findNum(nums):
        ones=twos=threes=0
        for i in range(len(nums)):
                twos |= ones & A[i]
                ones ^= A[i]
                threes = ones & twos
                ones &= ~threes
                twos &= ~threes
        return ones

### 第4题：先将数组所有数字异或，最后结果就是两个出现一次的数字相互异或的结果，再将这两个数分别分在两个数组中进行异或。

设题目中这两个只出现1次的数字分别为A和B，如果能将A，B分开到二个数组中，那显然符合“异或”解法的关键点了。因此这个题目的关键点就是将A，B分开到二个数组中。**由于A，B肯定是不相等的，因此在二进制上必定有一位是不同的。根据这一位是0还是1可以将A，B分开到A组和B组。**而这个数组中其它数字要么就属于A组，要么就属于B组。再对A组和B组分别执行“异或”解法就可以得到A，B了。而要判断A，B在哪一位上不相同，只要根据A异或B的结果就可以知道了，这个结果在二进制上为1的位都说明A，B在这一位上是不相同的。

比如int a\[\] = \{1, 1, 3, 5, 2, 2\}

整个数组异或的结果为3^5即 0x0011 ^ 0x0101 = 0x0110

对0x0110，第1位（由低向高，从0开始）就是1。因此整个数组根据第1位是0还是1分成两组。

a\[0\] =1  0x0001  第一组

a\[1\] =1  0x0001  第一组

a\[2\] =3  0x0011  第二组

a\[3\] =5  0x0101  第一组

a\[4\] =2  0x0010  第二组

a\[5\] =2  0x0010  第二组

第一组有\{1, 1, 5\}，第二组有\{3, 2, 3\}，明显对这二组分别执行“异或”解法就可以得到5和3了。

def findNum(nums):
        if not nums:
            return -1
        temp=0
        ##先所有数异或得到A^B的值，A和B为只出现一次的数
        for item in nums:
            temp^=item
        #找到A和B不同的第一位，A^B的第一个1位。该位设为j位
        j=0
        while j<32:
            if (temp>>j)&1==1:
                break
            j+=1
        A=[]
        B=[]
        #将A、B分到按第j位不同分到不同组A和B
        for num in nums:
            if (num>>j)&1==1:
                A.append(num)
            else:
                B.append(num)
        ##分到的两个组全部都异或
        resA=0
        resB=0
        for itemA in A:
            resA^=itemA
        for itemB in B:
            resB^=itemB
        return resA,resB
    nums=[1,1,3,5,2,2]
    print(findNum(nums))

第5题：思路1：list(set(range(1,1001))-set(nums))，即两个集合相减

思路2：将nums中相对应的数变为负数，最后两个正数为所求。