LeetCode 137. 只出现一次的数字 II

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 137. 只出现一次的数字 II 原题链接中等

作者：

wzc1995 , 2018-05-30 14:53:19 , 所有人可见 , 阅读 3656

35

12

题目描述

给你一个整数数组 nums，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。

样例

输入：nums = [2,2,3,2]
输出：3

输入：nums = [0,1,0,1,0,1,99]
输出：99

限制

1 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次。

算法

(位运算) $O(n \log s)$

根据 Single Number 的做法，可以推广到更一般的问题。
考虑二进制每一位上出现 0 和 1 的次数，如果出现 1 的次数为 3k + 1，则证明答案中这一位是 1。

时间复杂度

遍历 $O(\log s)$ 次数组，故时间复杂度为 $O(n \log s)$，其中 $s$ 是最大可能的数字范围。

空间复杂度

仅需要常数的额外空间。

C++ 代码 1

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;

        for (int bit = 0; bit < 32; bit++) {
            int c = 0;

            for (int x : nums)
                c += (x >> bit) & 1;

            ans |= (c % 3) << bit;
        }

        return ans;
    }
};

9 评论

500k 2023-06-21 11:46

O(nlogs) s这里是什么？不是遍历了32次数组吗？

wzc1995 2023-06-21 14:12

$s$ 是最大可能的数字，放在这里最多是遍历 32 次数组

500k 2023-06-21 10:46

啊啊啊啊啊，为啥python过不去啊？

    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for bit in range(32):
            counter = 0
            for num in nums:
                counter += (num >> bit) & 1
            ans += (counter % 3) << bit

        return ans

Input
nums =
[-2,-2,1,1,4,1,4,4,-4,-2]
Output
4294967292
Expected
-4

wzc1995 2023-06-21 14:42

python 和 cpp 处理整型不太一样，由于数组中存在负数，cpp 区分普通整型和无符号整型，区别在于二进制最高位的 1 是负数补码还是普通的二进制位，而在 python 中没有这个概念，所以 python 的代码需要在大于等于 $2^{31}$ 时，减去 $2^{32}$ 换算到负数。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for bit in range(32):
            counter = 0
            for num in nums:
                counter += (num >> bit) & 1
            ans += (counter % 3) << bit

        if ans >= 2**31:
            ans -= 2**32

        return ans