首页 > 其他 > 详细

Single Number II

时间:2018-06-17 14:51:05      阅读:167      评论:0      收藏:0      [点我收藏+]

2018-06-17 14:04:27

问题描述:

技术分享图片

问题求解:

方法一、如果对空间复杂度没有要求,那么直接使用HashMap对每个数字出现次数进行计数,最后对HashMap遍历一遍即可,总的时间复杂度为O(n),空间开销较大。

方法二、对空间要求比较严格的话,那就只能使用位运算了,一个简明的思路是,对于所有出现三次的数,其各个位置上1出现的次数也是3的倍数,可以利用这点来进行判断。

public class SingleNumberII {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int mask = 1;
            int cnt = 0;
            mask = mask << i;
            for (int j = 0; j < nums.length; j++) {
                if ((nums[j] & mask) != 0) cnt++;
            }
            if (cnt % 3 != 0) res |= mask;
        }
        return res;
    }
}

方法三、上面的解法系数较大,可以进一步对其简化。核心思路依然是位运算,这里引入两个变量,ones 和 twos。ones:记录到当前计算的变量为止,二进制1出现“1次”(mod 3 之后的 1)的数位。

twos:记录到当前计算的变量为止,二进制1出现“2次”(mod 3 之后的 2)的数位。

当ones和twos中的某一位同时为1时表示二进制1出现3次,此时需要清零。即用二进制模拟三进制计算。最终ones记录的是最终结果。

    public int singleNumberII(int[] nums) {
        int ones = 0;
        int twos = 0;
        int xthree = 0;
        for (int num : nums) {
            twos |= (ones & num);
            ones ^= num;
            xthree = ~(twos & ones);
            ones &= xthree;
            twos &= xthree;
        }
        return ones;
    }

 

Single Number II

原文:https://www.cnblogs.com/TIMHY/p/9192819.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!