寻找数组中只出现一次的数

有三个类似的问题，分别是

1、数组中除了一个数只出现一次，其他所有数都成对出现。

这个问题的解法是将所有数异或，然后得到的结果就是我们要求的数。

2、数组中有两个数只出现一次，其他数都成对出现。

解法是先将所有的数进行异或，得到一个中间值。这个值为两个不同数异或的结果。

然后找到为1的位，这个位代表这两个数不相同的位。

然后根据它与两个数异或，将这两个数分到两个不同的数组里。问题就转化成第一个问题了。然后可以得出结果。

3、数组中除了一个数只出现一次，其他所有数都出现三次，找出这个数

解法是将每个数的某一位（0 或者 1）提取出来，进行相加。如果最后得到的和对3取余的结果为1，只出现一次的数该位为1。

然后可以得出要求的数。

三个问题的代码如下

int singleNumber(vector<int>& nums) {
        int result = 0;
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            result ^= nums[i];
        }
        return result;
    }

vector<int> singleNumber(vector<int>& nums) {
        int middle = 0;
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            middle ^= nums[i];
        }
        int flag = 1;
        while(!(flag & middle))
            flag <<= 1;
        vector<int> result(2, 0);
        
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] & flag)
            {
                result[0] ^= nums[i];
            }
            else
                result[1] ^= nums[i];
        }
        
        return result;
    }

 int singleNumber(vector<int>& nums) {
        int result = 0;
        
        for(int i = 0; i < 32; ++i)
        {
            int sum = 0;
            
            for(int j = 0; j < nums.size(); ++j)
            {
                sum += ((nums[j] >> i) & 1);
            }
            
            if(sum % 3 == 1) result |= (1 << i);
        }
        
        return result;
    }

最后

以上就是无限康乃馨为你收集整理的寻找数组中只出现一次的数的全部内容，希望文章能够帮你解决寻找数组中只出现一次的数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。