Medium

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

这道题是经典的位运算问题，有几种解法思路：

方法一：数字电路状态机（推荐） 我们需要设计一个状态机来统计每个位上1的个数。用两个变量 ones 和 twos 来记录：

  • ones：记录出现1次的位
  • twos：记录出现2次的位

当某个位出现3次时，我们需要将其清零。状态转换规律：

  • 第一次出现：ones 记录，twos 不变
  • 第二次出现：ones 清零，twos 记录
  • 第三次出现：ones 和 twos 都清零

方法二：按位统计 对于每一位，统计所有数字在该位上1的个数。如果某位上1的个数不是3的倍数，说明只出现一次的数字在该位上是1。

方法三：哈希表计数 使用哈希表统计每个数字的出现次数，找出出现1次的数字。但空间复杂度为O(n)，不满足题目要求。

这里采用方法一，它巧妙地利用位运算实现了O(1)空间复杂度的解法。

代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
};

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones = twos = 0
        for num in nums:
            ones = (ones ^ num) & ~twos
            twos = (twos ^ num) & ~ones
        return ones

public class Solution {
    public int SingleNumber(int[] nums) {
        int ones = 0, twos = 0;
        foreach (int num in nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
}

var singleNumber = function(nums) {
    let ones = 0, twos = 0;
    for (let num of nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    return ones;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型推荐解法
时间复杂度O(n)
空间复杂度O(1)

相关题目