当前位置: 首页 > news >正文

剑指offer56_数组中唯一只出现一次的数字

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


在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

思考题:

  • 如果要求只使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢?
数据范围

数组长度 [1,1500]。
数组内元素取值范围 [0,1000]。

样例
输入:[1,1,1,2,2,2,3,4,4,4]输出:3

算法思路

核心思路是使用位运算状态机的概念,通过两个变量(ab)记录每个比特位出现次数的状态(模 3 的结果)。状态转移规则如下:

  • 状态定义:用 (b, a) 表示每个比特位的状态:
    • 00:该位出现次数为 0 或 3 的倍数。
    • 01:该位出现 1 次。
    • 10:该位出现 2 次。
  • 状态转移(输入当前数字 x 的某一位):
    • 输入 0:状态保持不变。
    • 输入 1:状态按 00 → 01 → 10 → 00 循环变化。
  • 更新规则
    • a = (a ^ x) & ~b
    • b = (b ^ x) & ~a(注意:此处 a 是已更新后的值)

最终,a 记录了所有出现一次的数字的比特位,即所求结果。

时间复杂度
  • O(n):遍历数组一次,n 为数组长度。
空间复杂度
  • O(1):仅使用两个额外变量 ab
class Solution {
public:int findNumberAppearingOnce(vector<int>& nums) {int a = 0, b = 0; // 初始化状态为 00for (auto x : nums) { // 遍历每个数字// 更新规则(注意顺序):// 1. 更新 a:利用当前状态 b 和输入 x//    - 当 b=0 时,a 与 x 异或(记录新状态)//    - 当 b=1 时,a 被置 0(状态 10 遇到 1 后变为 00)a = (a ^ x) & ~b;// 2. 更新 b:利用更新后的 a 和输入 x//    - 当 a=0 时,b 与 x 异或(记录新状态)//    - 当 a=1 时,b 被置 0(确保状态合法)b = (b ^ x) & ~a;}return a; // 最终 a 存储出现一次的数字}
};

实例演示

假设输入数组 nums = [2, 2, 3, 2],所有数字的二进制表示:

  • 2010
  • 3011

逐步计算每个比特位的状态变化:

最低位(LSB)
  1. 输入 0(来自 2):
    • 初始状态 (b,a) = (0,0)
    • 更新后:a = (0^0)&~0 = 0, b = (0^0)&~0 = 0 → 状态 00
  2. 输入 0(来自 2):状态保持 00
  3. 输入 1(来自 3):
    • a = (0^1)&~0 = 1, b = (0^1)&~1 = 0 → 状态 01
  4. 输入 0(来自 2):状态保持 01
    • 最终状态 01 → 该位为 1
中间位
  1. 输入 1(来自 2):
    • a = (0^1)&~0 = 1, b = (0^1)&~1 = 0 → 状态 01
  2. 输入 1(来自 2):
    • a = (1^1)&~0 = 0, b = (0^1)&~0 = 1 → 状态 10
  3. 输入 1(来自 3):
    • a = (0^1)&~1 = 0, b = (1^1)&~0 = 0 → 状态 00
  4. 输入 1(来自 2):
    • a = (0^1)&~0 = 1, b = (0^1)&~1 = 0 → 状态 01
    • 最终状态 01 → 该位为 1
最高位
  1. 输入 0(来自 2):状态保持 00
  2. 输入 0(来自 2):状态保持 00
  3. 输入 0(来自 3):状态保持 00
  4. 输入 0(来自 2):状态保持 00
    • 最终状态 00 → 该位为 0

最终结果:二进制 011 = 十进制 3
输出:3(符合预期)。

http://www.xdnf.cn/news/1109107.html

相关文章:

  • 【MogDB】一种基于ctid分片并发查询以提升大表查询性能的方式
  • 【go】gopath、GO111MODULE=on作用
  • Javaweb- 11 MVC架构模式
  • JDK官方文档下载教程
  • 计算机视觉 之 经典模型汇总
  • 快速排序递归和非递归方法的简单介绍
  • 牛客:HJ19 简单错误记录[华为机考][字符串]
  • phpstudy搭建pikachu靶场
  • CCS-MSPM0G3507-2-定时器中断
  • SpringAI实现保存聊天记录到redis中
  • C++单元测试gtest技术
  • RHCSA(2)
  • 云端docker小知识
  • sqli-labs靶场通关笔记:第7-8关 布尔盲注
  • 一文理解锂电池充电、过放修复与电量测量:从原理到实战
  • Ubuntu安装Jenkins
  • 具身智能最有前景的方向之一“在线强化学习”新突破
  • arcgis投影后数据显示问题记录
  • 贪心算法题解——跳跃游戏 II【LeetCode】
  • 死锁的避免
  • LangChain 内存(Memory)
  • 创建uniapp项目引入uni-id用户体系使用beforeRegister钩子创建默认昵称
  • 9. JVM垃圾回收
  • 12. JVM的垃圾回收器
  • Agent 设计模式
  • 前后端分离项目的完整部署(Jenkins自动化部署)
  • 【从零开始编写数据库:基于Python语言实现数据库ToyDB的ACID特性】
  • 27.【.NET8 实战--孢子记账--从单体到微服务--转向微服务】--单体转微服务--币种服务(一)
  • Android下一个简单的定时器,每隔一秒输出一个数字
  • Syntax Error: TypeError: Cannot set properties of undefined (setting ‘parent‘)