137.Single Number II(只出现一次的数字II)(MId)

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:

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

Example 2:

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

解：LeetCode上260、136、137这三道题都是有关统计数字出现次数的问题，其中136最简单，因为除了一个数字，其他数字都出现2次(或者偶数次)，那么完美符合用异或的情况。

一个数字异或它本身之后为0；0异或任何数字都为那个数字本身，所以136对每个数字求异或之后即可得到目标数字。过程在这里省略。

136题的代码：

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for(int num : nums) {
            result = result^num;
        }
        return result;
    }
}

回到本题，因为除了1个数字只出现1次，其他所有数字都出现3次，所以这道题不能用单纯的异或来计算了。

方法一：Map。这个方法开辟了新的空间，只能说可行，但是在空间复杂度上遜于位运算。

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums) {
            map.put(num, map.getOrDefault(num,0) + 1);
        }
        
        for(int key : map.keySet()) {
            if(map.get(key) == 1) {
                return key;
            }
        }
        return -1;
    }
}

方法二：位运算，参考这篇题解

如果我们把每个数字都用二进制形式列出来，会发现出现了3次的数字的每一列之和都会是3的倍数。之所以有的列不是3的倍数，是因为出现了1次的数字的那一位1单独贡献了次数。

所以，所有出现次数不是3的倍数的列全部写成1，出现1次数是3倍数的列写0，就能找到这个出现了1次的数。

class Solution {
    public int singleNumber(int[] nums) {
        int result=0;
        // 整数数组，遍历32位
        for(int i = 0; i < 32; i++) {
            int count = 0;
            // 考虑每一位个数
            for(int j = 0; j < nums.length; j++) {
                //获取nums[j]的第i位值(0或1),如果其为1，count++
                // 利用位运算经典公式(x >> n) & 1
                if((nums[j] >> i & 1) == 1) {
                    count++;
                    // 这里可以变通，如果题目改一下，除了一个数字出现一次，
                    // 其他的都出现5次，求一样的东西，把3换成5即可
                    count %= 3;
                }
            }
            //若当前count不为3的倍数，利用位运算经典操作将这一位赋值给result
            // 仅将第i位置为1,其他都为0。因为只有一个出现1次的数字，所以count不是0就是1
            if(count != 0) {
                result = result | (count << i);
            }
        }
        return result;
    }
}

方法三：LeetCode上高票答案

public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
}

260.Single Number III(只出现一次的数字III)(MId)

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

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

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

解：题目大意是，只有两个数出现了1次，其他数都出现2次，我们要找到这个数。

这道题是136的变化，出现1次的数字从1个变到了2个，其他数字出现次数没变，还是2次。

核心思想是把nums分成两部分，怎么分呢？

先将所有数异或一下，最后得到的是两个目标值异或的结果。因为这两个数都只出现了1次，所以他俩异或的结果一定不是0，而且异或之后，他俩不同的位的地方都会为1.

然后获取他俩异或结果的最低位1，利用位运算经典公式：x&(-x)——和负数与的时候，负数要取反加1

class Solution {
    public int[] singleNumber(int[] nums) {
        // 保存最后一个非零位
        int mask = 0;
        // 求出目标的两个数字的异或结果
        for(int num : nums) {
            mask ^= num;
        }
        // 记录异或之后最低的非零位的位置
        int lastOnePos = mask & (-mask);
        // 最终返回的结果
        int[] result = new int[2];
        // 重新遍历一遍nums，如果最低位与之前的最低位一样都是1，则划为一个数组
        // 如果不一样，划为另一个数组
        // 因为目标两个数都只出现了一次，所以根据这个划分可以得到各自包含他们俩的两个数组
        for(int num : nums) {
            if((num & lastOnePos) == 0) {
                result[0] ^= num;
            } else {
                result[1] ^= num;
            }
        }
        return result;
    }
}

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