AcWing 74. 数组中唯一只出现一次的数字 - AcWing

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 74. 数组中唯一只出现一次的数字原题链接中等

作者：

Sherry_ , 2019-06-27 20:18:41 , 所有人可见 , 阅读 3639

35

5

算法

看每一位1的数量

C++ 代码

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int ans = 0;
        for (int i = 31; i >= 0; --i) {
            int cnt = 0;
            for (int x: nums) {
                if (x >> i & 1) {
                    cnt ++;
                }
            }
            if (cnt % 3 == 1) {
                ans = (ans * 2) + 1;
            }
            else {
                ans = ans * 2;
            }
        }
        return ans;
    }
};

15 评论

Anoxia_3 2021-07-23 10:11

回复

那你这个就是O(nlogn)时间复杂度了

computics 2021-10-14 14:21

回复

外层循环是常数，还是O(n)吧

艹蛋の圊舂じ讓涐蛋疼ミ 13天前

回复

秀

dp好难 2022-06-02 10:15

回复

能讲一讲算法思想吗，只看代码看不透

Ice_spring 2022-06-08 23:40

回复

int 共32位，统计在每一位上 1 出现的次数，如果数是重复 3 次的，相应位上 1 的个数模 3 肯定为 0，如果模 3 为 1 ，一定是那个只出现一次的数留下的，用所有 1 出现的二进制位恢复那个只出现一次的数就好了。

evan_zhu 2021-09-10 16:22

回复

秀

j简单 2021-05-23 21:44

回复

妙哉！

Sakura1996 2021-01-15 22:15

回复

判断可写成一句：ans = (ans << 1) + (cnt % 3);

glimmer 2021-05-22 22:49

回复

大神这句怎么解释？ ans和cnt的关系

dp好难 2022-06-02 10:09 回复了 glimmer 的评论

回复

ans总是需要乘以2倍的，但是cnt如果是奇数的话那么cnt%3就是+ 1，如果是偶数的话那么 + 0

Hidder 2020-10-28 22:03

回复

nb

goldstine 2020-10-06 22:44

回复

orz

HyperMn 2020-08-18 20:39

回复

妙

葱花鸡蛋 2020-04-28 14:35

回复

厉害的

晓玲 2020-04-11 10:46

回复

OTZ,这个思想很巧妙