Single Number II

发表于   |   分类于 ， ，

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

描述

数组内除了一个数外，其余数都出现 3 次，找出那个数

分析

以二进制的形式来考虑

一般方法：一个数出现 k 次，可以看成其二进制的第 i 位出现了 k 次，不论第 i 位是 0 或是 1，累加起来，取余 k 后，必定为 0，剩下的便是唯一的一个数

优化方法：不再将数细分成二进制的每一位，而是看作一个整体来统一处理。one，two，three 分别代表这个数出现的次数，three = (two & one) 相当于 3 = 2 + 1。~three 则相当于 three % 3，之后再更新 one 和 two 即可

代码

一般方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int singleNumber(int[] nums) {

        int n = nums.length;
        int[] count = new int[32];
        int result = 0;

        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < n; j++) {
                if (((nums[j] >> i) & 1) == 1) {
                    count[i]++;
                }
            }
            result |= ((count[i] % 3) << i);
        }

        return result;
    }
}

优化方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int singleNumber(int[] nums) {

        int n = nums.length;
        int one = 0, two = 0, three;

        for (int i = 0; i < n; i++) {
            two |= (one & nums[i]);
            one ^= nums[i];
            three = (two & one);
            one &= (~three);
            two &= (~three);
        }

        return one | two;
    }
}