只出现一次的数字——2个解题猜想

问题描述

只出现一次的数字

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
示例 1：

输入：nums = [2,2,3,2]
输出：3
示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

问题分析

猜想1：计数方法
其余元素出现三次，这样一来异或就不能用了，那我们可以使用计数来实现
遍历一次数组后返回只有一次计数的元素

猜想2：延续异或消除其余数的方法
方法1：
我们用循环模拟可以叠加到3的bit位，
设变量n
然后将所有数的各个比特位在对应位置叠加，并存储在n，
接着把n的各个比特位%3，如此即可消除所有出现了3次的数。
最后n就等于只出现了一次的数

方法2：
虽然直接异或不能用了，但是其余元素出现3次意味着，它们一定会触发一次异或，
那我们对触发异或的位置做标记，最后找没有触发异或的数即可；

解决方案

代码

猜想2方法1成功：

//  猜想2：延续异或消除其余数的方法
//  方法1：
//  我们用循环模拟可以叠加到3的bit位，
//  设变量n
//  然后将所有数的各个比特位在对应位置叠加，并存储在n，
//  接着把n的各个比特位%3，如此即可消除所有出现了3次的数。
//  最后n就等于只出现了一次的数
class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret=0;
        for(int i=0;i<32;i++)
        {
            int n=0;

            //把nums的所有数的第i个bit位叠加到n的第i个比特位上
            for(int x:nums)
            {
                n+=x>>i&1;
            }

            //用ret接收%后的结果，
            //循环结束后ret的各个位就是只出现一次的那个数了
            ret|=n%3<<i;
        }
        return ret;
    }
};

猜想1失败：

//  猜想1：计数————做不出来，失败，遍历有问题
// class Solution 
// {
// public:
//     int singleNumber(vector<int>& nums) 
//     {
//         iterator it =nums.iterator();
//         //建立一个数组，用来计数
//         //数组的大小为nums数组的最大的那个数字
//         vector<int> arr(max(nums),0); 
//         //遍历一遍，把重复元素以计数形式标出来
//         while(it)
//         {
//             arr[*it]++;
//             it++;
//         }
//         for(auto arr:ch2)
//         {
//             if(arr[ch2]==1)
//             {
//                 return ch2;
//             }
//         }
//         //找到数组里最大的那个数
//         int max(const nums)
//         {
//             int max=0;
//             for(auto n:nums)
//             {
//                 if(n>max)
//                 {
//                     max=n;
//                 }
//             }
//             return max;
//         }
//     }
//};