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;}
};

常规题解——位运算做法

在这里插入图片描述

实现代码

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;
}

为什么要用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;
}

提交结果

在这里插入图片描述

变式题

这一题还可以继续扩展，在数组中每个元素都出现 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);
}