题目链接

牛客网

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次，找出这两个数。

解题思路

方法一：哈希法

通过map记录每个数字的个数，找出个数为1的数字。空间复杂度高。

  1. class Solution {
  2. public:
  3.     void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
  4.         map<int,int> mp;
  5.         for(const int item : data){
  6.             auto it = mp.find(item);
  7.             if(it==mp.end()){
  8.                 mp[item] = 1;
  9.             }else{
  10.                 mp[item]++;
  11.             }
  12.         }
  13.         int flag=1;
  14.         for(const int item : data){
  15.             if(mp[item]!=1)
  16.                 continue;
  17.             else{
  18.                 if(flag==1){
  19.                     *num1=item;
  20.                     flag=0;
  21.                 }
  22.                 else
  23.                     *num2=item;
  24.             }
  25.         }
  26.     }
  27. };
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

    方法二：异或运算

两个相等的元素异或的结果为 0，而 0 与任意数 x 异或的结果都为 x。

对本题给的数组的所有元素执行异或操作，得到的是两个不存在重复的元素异或的结果。例如对于数组 [x,x,y,y,z,k]，xyz^k = 0yk = yz^k = 0k = z^k。

所以，我们可以让数组中的每一个数异或一下，最后会得到一个结果ret，就是两个出现一次的数字的异或结果这个结果肯定是由两个不同数字异或而来，因此我们找ret二进制中为1的位置i，因为1一定是由0,1异或而来，因此要求得两个数中，一定有一个数的二进制中的第i个位置为1， 一个为0.

如何找到位置i？可用i = ret & (-ret)
因为计算机用补码存取二进制数，而负数的补码为反码+1，举个例子
假如ret = 1110 ， -ret = 0010 , 所以 i = 0010
所以，再异或运算一遍即可得到答案。
位置i为1的相互异或运算，留下只出现一次并且位置i为1的数。
位置i为0的相互异或运算，留下只出现一次并且位置i为0的数。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int ret = 0;
        for (const int k : data) ret ^= k;
        ret &= (-ret);
        *num1 = 0, *num2 = 0;
        for (const int k : data) {
            if (k & ret) // 当前数位置i是否为1 
                *num1 ^= k;
            else 
                *num2 ^= k;
        }
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)