DeepSeek LeetCode 137.不出现一次的数字|| C语言实现

LeetCode 137 是 只出现一次的数字 II：数组中除某个元素只出现一次外，其余元素都出现三次，要求找出这个元素。

C 语言实现（位运算状态机，推荐）

intsingleNumber(int*nums,intnumsSize){intones=0;// 记录某二进制位出现 1 次的状态inttwos=0;// 记录某二进制位出现 2 次的状态for(inti=0;i<numsSize;i++){ones=(ones^nums[i])&~twos;twos=(twos^nums[i])&~ones;}returnones;}

思路简述

· ones 表示当前扫描过程中，二进制某位出现 1 次的情况。
· twos 表示二进制某位出现 2 次的情况。
· 当某一位出现 3 次时，ones 和 twos 都会把该位清零。
· 最终 ones 中留下的就是只出现一次的那个数的二进制位。

复杂度

· 时间复杂度：O(n)
· 空间复杂度：O(1)

另一种直观写法：逐位统计

intsingleNumber(int*nums,intnumsSize){unsignedintans=0;for(inti=0;i<32;i++){intcount=0;for(intj=0;j<numsSize;j++){count+=((unsignedint)nums[j]>>i)&1U;}if(count%3!=0){ans|=(1U<<i);}}return(int)ans;}

这种写法统计每个二进制位上 1 出现的次数，对 3 取模，剩下的位就组成只出现一次的数字。时间复杂度 O(32n)，也是 O(n)。