---
title: "数组中唯一只出现一次的数字"
created: 2025-11-28
tags:
  - 算法
---

# 数组中唯一只出现一次的数字

## 题目 [数组中唯一只出现一次的数字](https://www.acwing.com/problem/content/description/70/)

![[image-93be5d97.png]]

## 思路分析

状态机 构造状态 遇见1变下一个状态 遇见0自环

至于遇见1做什么操作 能实现状态只有三个 就……emmm

这种方法太难了 跳过吧

![[image-a1b0e121.png]]

详解见[力扣](https://leetcode.cn/problems/single-number-ii/solutions/1/single-number-ii-mo-ni-san-jin-zhi-fa-by-jin407891/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china) 这玩意y总也讲的不清楚
不给推出过程 只套一遍代码流程

需要的状态转移方式是，如果出现两个1就抵消为0，用一个变量和异或运算即可实现，而本题是需要1出现三次时才会抵消，因此有三种状态，即1出现的次数为3k,
3k + 1, 3k + 2次

逐个位来看，要设计一个两位的状态转移，出现三个1时，循环抵消，出现0时不变，一个变量只能记录两种状态，因此要用两个变量来记录状态，用one和two两个变量来记录1出现次数
00表示1出现3k次，01表示1出现3k + 1次，10表示1出现3k + 2次

真值表

![[image-7453cf54.png]]

先看one的状态转移方程

one = (~one & ~two & x) | (one & ~two & ~x)

= ~two & ((~one & x) | (one & ~x))

= ~two & (one ^ x)

同理，再用转移后的one来求two的状态转移方程

这里，one为当且仅当1出现次数为3k + 1, tow为当且仅当1出现次数为3k + 2 因此如果题目改为，有一个数出现了两次，则返回two即可

或者用第二种方式 **遍历统计** 好理解些（至于为什么能这样……还是不知道）

考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。 因此，统计所有数字的各二进制位中 1 的出现次数，并对
3 求余，结果则为只出现一次的数字。（还是不懂为什么可以这样 但是方法懂了）

![[image-9bbb5890.png]]

## 代码实现

**状态机**

```java
class Solution {

public:

    int findNumberAppearingOnce(vector<int>& nums) {

        int one=0,two=0;

        for(auto x:nums)

        {

            one=(one^x)&~two;

            two=(two^x)&~one;

        }

        return one;

    }

};
```

**遍历统计**

```java
class Solution {

public:

    int findNumberAppearingOnce(vector<int>& nums) {

        //建立一个长度为 32 的数组 counts 记录所有数字的各二进制位的 1 的出现次数。

        vector<int> counts(32, 0);

        for(int num : nums) {

            for(int j = 0; j < 32; j++) {

                counts[j] += num & 1;// 更新第 j 位 直接+=即可 是0的话也等于没加

                num >>= 1;

            }

        }

        int res = 0, m = 3;

        //将counts 各元素对 3 求余，则结果为 “只出现一次的数字” 的各二进制位。

        //将counts数组中各二进位的值恢复到数字 resresres 上

        //(循环区间是 i∈[0,31])

        for(int i = 0; i < 32; i++) {

            res <<= 1;

            res |= counts[31 - i] % m;

        }

        return res;

    }

};

//只需要修改求余数值m，即可实现解决除了一个数字以外，其余数字都出现m次的通用问题。
```

## 同类题型

## 视频讲解

---
⬅️ [[数组中只出现一次的两个数字|数组中只出现一次的两个数字]] 🏠 [[00-刷题理模型]] ➡️ [[进制|进制]]