Leetcode 题目解析之 Single Number II

原创

ruochen

发布于 2022-01-14 11:28:27

1.3K0

发布于 2022-01-14 11:28:27

文章被收录于专栏：若尘的技术专栏

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?

对于数组{1,1,1,2}来说，分析每一位：

0 0 0 1 
0 0 0 1 
0 0 0 1 
0 0 1 0 
…………… 
0 0 1 3 (位数)

可以分析，分别计算每一位1的出现次数n，如果n%3==1，那么结果中这一位就应该是1。

    public int singleNumber(int[] nums) {
        int rt = 0, bit = 1;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int v : nums) {
                if ((v & bit) != 0) {
                    count++;
                }
            }
            bit <<= 1;
            rt |= (count % 3) << i;
        }
        return rt;
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

element