Leetcode—137.只出现一次的数字II【中等】

2023每日刷题（二）

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

没有满足空间复杂度的Map题解

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int>count;
        for(int iter: nums) {
            ++count[iter];
        }
        int ans = 0;
        for(auto [iter, cnt]: count) {
            if(cnt == 1) {
                // return iter;
                ans = iter;
                break;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

常规题解——位运算做法

实现代码

int singleNumber(int* nums, int numsSize){
    int i, j;
    int opt[32] = {0};
    for(i = 0; i < numsSize; i++) {
        for(j = sizeof(int) * 8 - 1; j >= 0 ; j--) {
            opt[j] += nums[i] & 1;
            nums[i] >>= 1;
        }
    }
    int k = 0;
    unsigned int res = (unsigned int)0;
    for(; k < sizeof(int) * 8; k++) {
        res <<= 1;
        res |= opt[k] % 3;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

为什么要用unsigned int呢，因为或左移溢出报错，例如，
Line 13: Char 13: runtime error: left shift of 2147483646 by 1 places cannot be represented in type ‘int’ [solution.c]

左移的高位如果超过符号位，就会报错。因此要用类型强制转换来unsigned来接住。

提交结果

有限状态自动机FSM+位运算法

解题思想

参考的是这两位大佬的博客，一个是k神





还有灵茶山艾府大神的，很有启发！

实现代码

int singleNumber(int* nums, int numsSize){
    int a = 0, b = 0;
    int i;
    int tmp = a;
    for(i = 0; i < numsSize; i++) {
        a = (a ^ nums[i]) & (a | b);
        b = (b ^ nums[i]) & ~tmp;
        tmp = a;
    }
    return b;
}
1
2
3
4
5
6
7
8
9
10
11

提交结果

变式题

这一题还可以继续扩展，在数组中每个元素都出现 5 次，找出只出现 1 次的数。那该怎么做呢？思路还是一样的，模拟一个五进制，5 次就会消除。

int singleNumber(int* nums, int numsSize){
    int i, a, b, c, tmpa, tmpb, tmpc;
    a = 0;
    b = 0;
    c = 0;
    for(i = 0; i < numsSize; i++) {
        tmpa = a;
        tmpb = b;
        tmpc = c;
        a = (a ^ nums[i]) & (b & c);
        b = ((b ^ nums[i]) ^ (~(tmpa | c))) & (~tmpa);
        c = (c ^ nums[i]) & (~tmpa);
    }
    return c;
}

int main()
{
    int x;
    int arr[11] = {9, 9, 9, 9, 9, 5, 3, 3, 3, 3, 3};
    x = singleNumber(arr, 11);
    printf("%d\n", x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！