【Day04】137.只出现一次的数字II

137. 只出现一次的数字 II

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

示例1:

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

示例2:

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

提示:

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • nums 中,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次

题解:

有限状态自动机:

使用二进制表示每个元素,对应二进制位的1相加,最后相加对3取余

对于所有数字中的某二进制位 1 的个数,存在 3 种状态,即对 3 余数为 0,1,2 。由于二进制只能表示 0, 10,1 ,因此需要使用两个二进制位来表示 3 个状态。设此两位分别为 one,two.

计算 one方法:

设当前状态为 one ,two 此时输入二进制位 nn 。如下图所示,通过对状态表的情况拆分,可推出 one的计算方法为:

if two == 0:
  if n == 0:
    one = one
  if n == 1:
    one = ~one
if two == 1:
    one = 0

引入 异或运算 ,可将以上拆分简化为:

if two == 0:
    one = one ^ n
if two == 1:
    one = 0

引入 与运算 ,可继续简化为:

one = one ^ n & ~two

同理:

two = two ^ n & ~one

代码:

class Solution {
public:
    int singleNumber(vector& nums) {
        int two = 0, one = 0;
        for (auto x: nums) {
            one = (one ^ x) & ~two;
            two = (two ^ x) & ~one;
        }
        return one;
    }
};

哈希表:

class Solution {
public:
    int singleNumber(vector& nums) {
        unordered_map um;
        for (auto x : nums) {
            um[x]++;
        }

        for (auto x : um) {
            if (x.second == 1) return x.first;
        }
        return -1;
    }
};

   转载规则


《【Day04】137.只出现一次的数字II》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day05】690.员工的重要性 【Day05】690.员工的重要性
690. 员工的重要性给定一个保存员工信息的数据结构,它包含了员工 唯一的 id ,重要度 和 直系下属的 id 。 比如,员工 1 是员工 2 的领导,员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。那么员工
2021-05-01
下一篇 
【Day03】403.青蛙过河 【Day03】403.青蛙过河
403. 青蛙过河题目描述: 一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。 给你石子的位置列表 stones(用单元格序号 升序 表示)
2021-04-29
  目录