# 问题 原题链接：https://leetcode.com/problems/single-number-ii/ Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: - Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? # 分析过程 - 输入：一个整数数组，所有数字都出现了三次，只有一个数字出现了一次。 - 输出：找到这个只出现了一次的数。 - 思路：任何出现了三次的数字，每一位加起来不是 0 就是 3，和 3 取模都是 0。某个数字只出现了一次，那么就会出现某一位和 3 取模余 1，这个 1 就是只出现了一次的数字的。对 3 取模的过程可以写成位运算，见注释。 # 解决方法 ```cpp class Solution { public: int singleNumber(vector<int>& nums) { // 00 + 1 = 01 // 01 + 1 = 10 // 10 + 1 = 00 相当于对 3 取模 // 写成位运算的形式如下 int a = 0, b = 0; for (int num : nums) { b = (b ^ num) & ~a; a = (a ^ num) & ~b; } return b; } }; ```