LeetCode 137. Single Number II

[Woodyiiiiiii]

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?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

---

题目大意是在一个非空数组中，一个数出现一次，其他数都出现三次，找出这个只出现一次的数。要求时间复杂度为O(n)，空间复杂度为O(1)。

按照位运算的思路，对每一位数相加后余3，得到的位数结果就是那个要找的数的位数。

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (int j = 0; j < nums.length; ++j) {
                sum += (nums[j] >> i) & 1;
            }
            // result += (sum % 3) << i;
            result |= (sum % 3) << i;
        }
        
        return result;
    }
}

注意要获取每一位数，都要>>右移后与1，最后左移。

扩展：如果其他数出现的次数是n次(n是奇数且大于等于3)，只需要改动余数就行，从%3改成%n。

参考资料：
LeetCode原题