LeetCode 137 是 只出现一次的数字 II数组中除某个元素只出现一次外其余元素都出现三次要求找出这个元素。C 语言实现位运算状态机推荐intsingleNumber(int*nums,intnumsSize){intones0;// 记录某二进制位出现 1 次的状态inttwos0;// 记录某二进制位出现 2 次的状态for(inti0;inumsSize;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){unsignedintans0;for(inti0;i32;i){intcount0;for(intj0;jnumsSize;j){count((unsignedint)nums[j]i)1U;}if(count%3!0){ans|(1Ui);}}return(int)ans;}这种写法统计每个二进制位上 1 出现的次数对 3 取模剩下的位就组成只出现一次的数字。时间复杂度 O(32n)也是 O(n)。