目录

题目描述：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]输出: 99

---

解法：

class Solution {public:    // method 2: FSM(finite state machine)    int singleNumber2(vector
    
     & nums){        // a, b, c        // 0 -> 1 -> 2 -> 0        // a -> b -> c -> a        int a = 0;  // 101101        int b = 0;  // 101101        int c = 0;  // 101101        int carry = 0;        for(int val : nums){            carry = a&val;            a |= val;            val = carry;                        carry = b&val;            b |= val;            val = carry;                        c = val;                        // when c has ones, then reset ones in a and b            a = a ^(a&c);            b = b ^(b&c);        }        return a;    }        // method 1:    int singleNumber1(vector
     
      & nums) {        vector
      
        bits(32, 0);        for(int val : nums){            for(int i = 0; i < 32; i++){                if(val&1){                    bits[i]++;                }                val >>= 1;            }        }        int res = 0;        for(int i = 31; i >= 0; i--){            res <<= 1;            if(bits[i]%3){                res += 1;            }        }        return res;    }        int singleNumber(vector
       
        & nums) {        return singleNumber2(nums);    }};