LeetCode —— 137. 只出现一次的数字 II

137. 只出现一次的数字 II

下面是错误的写法，没有考虑时间和空间复杂度。

// // //复杂度不行 可能是因为递归层次太深，递归每次都会在栈开空间，最会情况就是开n次
// class Solution {
// public:
//     int singleNumber(vector<int>& nums) {
//         sort(nums.begin(), nums.end());
//         int i = 0;
//         if(nums[0] != nums[1])
//             return nums[0];
//         i += 3;
//         while(i < nums.size() - 1)
//         {   
//             if(nums[i] != nums[i + 1])
//                 return nums[i];
//             i += 3;
//         }
//         return nums.back();
//     }
// };

正确解法

//分别将这些数对应二进制位的1有几个存到整型数组p中，然后分别 % 3，是3的倍数的就没了
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        size_t arr[32] = {0};
        size_t a = 1;
        int flag = 0;
        int special = 0;
        for(auto x: nums)//存1
        {
            if(x < 0)
            {
                if(x == -2147483648)//这样也不行，因为这个形参里面的类型int，最小的负数转为正数就越界了，比如char，最大 127，最小-128
                {
                    x += 1;
                    special++;
                }
                x *= -1;//负数变成补码就反了一下，不适合了。   
                flag++;

            }
            for(int i = 0; i < 32; i++)
            {

                if(((a << i) & x) != 0)
                {

                    arr[i]++;
                }
            }
        }

        int num = 0;
        int system = 31;
        for(int i = 0; i < 32; i++)
        {
            if(i == 31)
            {
                cout  << "进来了" << endl;
                arr[i] %= 3;
            }
            if(arr[i] % 3 != 0)
            {
                num += pow(2, i); 
            }
        }
        if(flag % 3 != 0)
            num *= -1;
        if(special == 1)
            num--;
        return num;

    }
};

• 博主长期更新，博主的目标是不断提升阅读体验和内容质量，如果你喜欢博主的文章，请点个赞或者关注博主支持一波，我会更加努力的为你呈现精彩的内容。