137. 只出现一次的数字 II

题目链接:https://leetcode-cn.com/problems/single-number-ii/

思路:考虑所有数在32位二进制的情况下的每一位1或0的个数。因为三个数是一样的,所以当前位是3*x个1+03*x个1+1  x∈(当前位是1的数的个数/3,是非负整数)这两种情况,这样可以看出统计一下每一位1的个数对3取余,就可以得到出现一次的那个数的当前位是1还是0,最后或起来即可。

举例:0 0 1 0 1 3 1 转换成二进制为:

0000000000000000000000000000000

0000000000000000000000000000000

0000000000000000000000000000001

0000000000000000000000000000000

0000000000000000000000000000001

0000000000000000000000000000011

0000000000000000000000000000001

每一位统计1个个数为:

0000000000000000000000000000014(这是每一位1的个数,是10进制表示)

然后每一位%3:

0000000000000000000000000000011    = 3

这样就得到这个值了(值是3),因为程序是一位一位做的,所以最后需要或( | )起来。

上代码:

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num : nums) {
                count += (num >> i) & 1;
            }
            result |= (count % 3) << i;
        }
        return result;
    }
}

 

上一篇:Unix时间戳(Unix timestamp)转换工具


下一篇:Minimum Time to Remove All Cars Containing Illegal Goods