LeetCode 137. 只出现一次的数字 II【哈希表;位运算;数字逻辑;DFA】中等

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个整数数组 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
  • nums 中,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次

可使用哈希映射统计数组中每个元素的出现次数。对于哈希映射中的每个键值对,键表示一个元素,值表示其出现的次数。在统计完成后,我们遍历哈希映射即可找出只出现一次的元素。这里不对代码进行说明。

解法1 依次确定每一个二进制位

为了方便叙述,我们称「只出现了一次的元素」为「答案」。

由于数组中的元素都在 i n t int int(即 32 32 32 位整数)范围内,因此可以依次计算答案的每一个二进制位是 0 0 0 还是 1 1 1

具体地,考虑答案的第 i i i 个二进制位( i i i 0 0 0 开始编号),它可能为 0 0 0 1 1 1。对于数组中非答案的元素,每一个元素都出现了 3 3 3 次,对应着第 i i i 个二进制位的 3 3 3 0 0 0 3 3 3 1 1 1,无论是哪一种情况,它们的和都是 3 3 3 的倍数(即和为 0 0 0 3 3 3。因此:

答案的 i i i 个二进制位,就是数组中所有元素的第 i i i 个二进制位之和除以 3 3 3 的余数

这样一来,对于数组中的每一个元素 x x x ,我们使用位运算 (x >> i) & 1 \texttt{(x >> i) \& 1} (x >> i) & 1 得到 x x x 的第 i i i 个二进制位,并将它们相加再对 3 3 3 取余,得到的结果一定为 0 0 0 1 1 1,即为答案的第 i i i 个二进制位

细节:需要注意的是,如果使用的语言对「有符号整数类型」和「无符号整数类型」没有区分,那么可能会得到错误的答案。这是因为「有符号整数类型」(即 int \texttt{int} int 类型)的第 31 31 31 个二进制位(即最高位)是补码意义下的符号位,对应着 − 2 31 -2^{31} 231 ,而「无符号整数类型」由于没有符号,第 31 31 31 个二进制位对应着 2 31 2^{31} 231 。因此在某些语言(例如 Python)中需要对最高位进行特殊判断。

class Solution {
public:int singleNumber(vector<int>& nums) {int ans = 0;for (int i = 0; i < 32; ++i) {int total = 0;for (int num : nums) total += ((num >> i) & 1); // 所有数的第i个二进制位之和if (total % 3) ans |= (1 << i); // 设置答案的第i个二进制位}return ans;}
};

复杂度分析:

  • 时间复杂度: O ( n log ⁡ C ) O(n \log C) O(nlogC) ,其中 n n n 是数组的长度, C C C 是元素的数据范围,在本题中 log ⁡ C = log ⁡ 2 32 = 32 \log C=\log 2^{32} = 32 logC=log232=32 ,也就是我们需要遍历第 0 ∼ 31 0\sim31 031 个二进制位。
  • 空间复杂度: O ( 1 ) O(1) O(1)

实际上本方法还可继续优化。我们设置三个数 o n e , t w o , t h r e e one, two, three one,two,three 分别表示所有元素的所有二进制位中出现一次、二次、三次的位。最后的 o n e one one 就是答案。过程如下,设 n u m num num 为当前元素:

  • 使用 o n e & n u m one\ \& \ num one & num 表示「 n u m num num o n e one one 中同时出现的二进制位」表示的值,这些二进制位目前出现了两次,因此 t w o ∣ = ( o n e & n u m ) two\ |=\ (one\ \&\ num) two = (one & num)
  • 使用 o n e x o r n u m one\ xor\ num one xor num ,这表示设置那些出现了一次的二进制位,出现了两次的二进制位会被置零。
  • 再令 o n e & t w o one\ \&\ two one & two 表示「 o n e one one t w o two two 中同时出现的二进制位」表示的值,这些二进制位目前出现了三次,令 t h r e e = ( o n e & t w o ) three = (one\ \&\ two) three=(one & two)
  • 相应的位出现了三次,则(和对 3 3 3 取余一样)将该位重置为 0 0 0 ——令 t w o & = t h r e e , o n e & = t h r e e two\ \&=\ ~three,\ one\ \&=\ ~three two &=  three, one &=  three

最后返回 o n e one one 作为答案,它记录了那些只出现一次的二进制位,在本题中就等于「答案」的值。

class Solution {
public: int singleNumber(vector<int>& nums) {int one = 0, two = 0, three;for (int num : nums) {// two的相应的位等于1,表示该位出现2次two |= (one & num);// one的相应的位等于1,表示该位出现1次one ^= num;// three的相应的位等于1,表示该位出现3次three = (one & two);// 如果相应的位出现3次,则该位重置为0two &= ~three;one &= ~three;}return one;}
};

解法2 数字电路设计

方法2以及后续进行优化的方法3需要有一定的数字电路设计的基础。需要对以下知识有一定的了解:

  • 简单的门电路(例如与门、异或门等)
  • 给定数字电路输入和输出(真值表),使用门电路设计出一种满足要求的数字电路结构

门电路表示:我们将会用到四种门电路,使用的符号如下:

  • 非门:我们用 A ′ A' A 表示输入为 A A A 的非门的输出;
  • 与门:我们用 A B AB AB 表示输入为 A A A B B B 的与门的输出。由于「与运算」具有结合律,因此如果同时用了多个与门(例如将 A A A B B B 进行与运算后,再和 C C C 进行与运算),我们可以将多个输入写在一起(例如 A B C ABC ABC );
  • 或门:我们用 A + B A+B A+B 表示输入为 A A A B B B 的或门的输出。同样地,多个或门可以写在一起(例如 A + B + C A+B+C A+B+C );
  • 异或门:我们用 A ⊕ B A\oplus B AB 表示输入为 A A A B B B 的异或门的输出。同样的,多个异或门可以写在一起(例如 A ⊕ B ⊕ C A\oplus B\oplus C ABC )。

在方法二中,我们是依次处理每一个二进制位的,那么时间复杂度中就引入了 O ( log ⁡ C ) O(\log C) O(logC) 这一项。既然我们在对两个整数进行普通的二元运算时,都是将它们看成整体进行处理的,那么我们是否能以普通的二元运算为基础,同时处理所有的二进制位

答案是可以的。我们可以使用一个「黑盒」存储当前遍历过的所有整数。「黑盒」的第 i i i 位为 { 0 , 1 , 2 } \{ 0, 1, 2 \} {0,1,2} 三者之一,表示当前遍历过的所有整数的第 i i i 位之和除以 3 3 3 的余数。但由于二进制表示中只有 0 0 0 1 1 1 而没有 2 2 2 ,因此我们可以考虑在「黑盒」中使用两个整数来进行存储,即:

黑盒中存储了两个整数 a a a b b b ,且会有三种情况:

  • a a a 的第 i i i 位为 0 0 0 b b b 的第 i i i 位为 0 0 0,表示 0 0 0
  • a a a 的第 i i i 位为 0 0 0 b b b 的第 i i i 位为 1 1 1,表示 1 1 1
  • a a a 的第 i i i 位为 1 1 1 b b b 的第 i i i 位为 0 0 0 ,表示 2 2 2

为了方便叙述,我们用 ( 00 ) (00) (00) 表示 a a a 的第 i i i 位为 0 0 0 b b b 的第 i i i 位为 0 0 0,其余的情况类似。

当我们遍历到一个新的整数 x x x 时,对于 x x x 的第 i i i x i x_i xi ,如果 x i = 0 x_i=0 xi=0 ,那么 a a a b b b 的第 i i i 位不变;如果 x i = 1 x_i=1 xi=1 ,那么 a a a b b b 的第 i i i 位按照 ( 00 ) → ( 01 ) → ( 10 ) → ( 00 ) (00)\to(01)\to(10)\to(00) (00)(01)(10)(00) 这一循环进行变化。因此我们可以得出下面的真值表:
270

当我们考虑输出为 a i a_i ai 时,根据真值表可以设计出电路:
a i = a i ′ b i x i + a i b i ′ x i ′ a_i = a_i'b_ix_i + a_ib_i'x_i' ai=aibixi+aibixi
当我们考虑输出为 b i b_i bi 时,根据真值表可以设计出电路:
b i = a i ′ b i ′ x i + a i ′ b i x i ′ = a i ′ ( b i ⊕ x i ) b_i = a_i'b_i'x_i + a_i'b_ix_i' = a_i'(b_i \oplus x_i) bi=aibixi+aibixi=ai(bixi)
将上面的电路逻辑运算转换为等价的整数位运算,最终的转换规则即为:

当我们遍历完数组中的所有元素后, ( a i b i ) (a_i b_i) (aibi) 要么是 ( 00 ) (00) (00) ,表示答案的第 i i i 位是 0 0 0;要么是 ( 01 ) (01) (01) ,表示答案的第 i i i 位是 1 1 1 。因此我们只需要返回 b b b 作为答案即可。

细节:由于电路中的 a i a_i ai​ 和 b i b_i bi 是「同时」得出结果的(同时根据旧有的 a , b a,b a,b 得到新的 a , b a,b a,b ),因此我们在计算 a a a b b b 时,需要使用临时变量暂存它们之前的值,再使用转换规则进行计算。

class Solution {
public:int singleNumber(vector<int>& nums) {int a = 0, b = 0;for (int num: nums) {tie(a, b) = pair{(~a & b & num) | (a & ~b & ~num), ~a & (b ^ num)};}return b;}
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n) ,其中 n n n 是数组的长度。
  • 空间复杂度: O ( 1 ) O(1) O(1)

解法3 数字电路设计优化

我们发现方法三中计算 b b b 的规则较为简单,而 a a a 的规则较为麻烦,因此可以将「同时计算」改为「分别计算」,即先计算出 b b b,再拿新的 b b b 值计算 a a a(这也是转换的实际情况)。

对于原始的真值表:
250
我们将第一列的 b i b_i bi​ 替换新的 b i b_i bi 即可得到:
250
根据真值表可以设计出电路:
a i = a i ′ b i ′ x i + a i b i ′ x i ′ = b i ′ ( a i ⊕ x i ) a_i = a_i'b_i'x_i + a_ib_i'x_i' = b_i'(a_i \oplus x_i) ai=aibixi+aibixi=bi(aixi)
这样就与 b i b_i bi​ 的电路逻辑非常类似了。最终的转换规则即为:

需要注意先计算 b b b,再计算 a a a

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

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n) ,其中 n n n 是数组的长度。
  • 空间复杂度: O ( 1 ) O(1) O(1)

解法4 DFA(余数状态转换)

如方法1所述,对于所有数字中的某二进制位 1 1 1 的个数,存在 3 3 3 种状态,即对 3 3 3 余数为 0 , 1 , 2 0, 1, 2 0,1,2

  • 若输入二进制位 1 1 1 ,则状态按照以下顺序转换;
  • 若输入二进制位 0 0 0 ,则状态不变
    0 → 1 → 2 → 0 → ⋯ 0 \rightarrow 1 \rightarrow 2 \rightarrow 0 \rightarrow \cdots 0120

    如下图所示,同样由于二进制只能表示 0 , 1 0, 1 0,1 ,因此需要使用两个二进制位来表示 3 3 3 个状态。设此两位分别为 t w o , o n e two , one two,one ,则状态转换变为:
    00 → 01 → 10 → 00 → ⋯ 00 \rightarrow 01 \rightarrow 10 \rightarrow 00 \rightarrow \cdots 00011000

    接下来通过状态转换表导出状态转换的计算公式
  • 计算 o n e one one 的方法:设当前状态为 t w o o n e two\ one two one ,此时输入二进制位 n n n 。如下图所示:
  • 计算 t w o two two 的方法:由于是先计算 o n e one one ,因此应在新 o n e one one 的基础上计算 t w o two two 。如下图所示,修改为新 o n e one one 后,得到了新的状态图。观察发现,可用同样的方法计算 t w o two two

以上是对数字的二进制中 “一位” 的分析,而 i n t int int 类型的其他 31 31 31 位具有相同的运算规则,因此可将以上公式直接套用在 32 32 32 位数上。

遍历完所有数字后,各二进制位都处于状态 00 00 00 和状态 01 01 01 (取决于 “只出现一次的数字” 的各二进制位是 1 1 1 还是 0 0 0 ),而此两状态是由 o n e one one 来记录的(此两状态下 t w o s twos twos 恒为 0 0 0 ),因此返回 o n e s ones ones 即可

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/160348.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

尚硅谷Docker核心技术

目录 第1课时 docker_前提知识要求和课程简介第2课时 docker_为什么会出现第3课时 docker_理念第4课时 docker_是什么&#xff1f;第5课时 docker_能干什么第6课时 docker_3要素第7课时 centos6安装Dockercentos7安装Docker第9课时 阿里云镜像加速器配置第10课时 helloworld镜像…

pycharm社区版创建Django项目的一种方式

pycharm社区版创建Django项目 pycharm创建New project安装django&#xff0c;如果安装过可略过安装完成后查看安装情况生成Django项目需要的文件这里注意生成语句后面的 . 不可以省略 生成文件后&#xff0c;框架搭建完成&#xff0c;配置启动我这里在配置完后&#xff0c;报了…

JAVAEE初阶相关内容第十四弹--网络初识

写在前&#xff1a; 这一部分开启网络部分的相关知识&#xff0c;这一弹内容初始网络将主要进行网络相关知识的简单介绍&#xff0c;以及着重介绍协议、协议分层、OSI七层模型、TCP/IP五层模型、封装和分用。 需要认识协议&#xff0c;并知道协议的效果是什么&#xff1b;知道…

RN(React Native)的应用程序在雷电模拟器可以运行,安卓真机运行失败问题解决记录

yarn react-native build-android打包的apk在真机安卓运行提示&#xff1a; Unable to load script . Make sure you re either running Metro ( run npx react - native start ) or that your bundle index . android . bundle is packaged correctly for release . jn…

微服务12-分布式服务理论基础+Seata的认识

文章目录 分布式服务理论基础前言微服务和分布式的区别CAP定理BASE理论 Seata流程&#xff1a;seata部署微服务集成seata 分布式服务理论基础 前言 单体架构&#xff1a; 1.项目过于臃肿&#xff0c;所有服务在一起&#xff0c;一个业务挂了&#xff0c;整个项目就不能用了&…

哪个牌子的电容笔好用?ipad触控笔推荐平价

有哪些电容笔适合学生党入手&#xff1f;苹果Pencil虽然与普通的电容笔&#xff0c;不同的是&#xff0c;这款电容笔同时具有重力传感器和倾斜传感器&#xff0c;而平替电容笔&#xff0c;只有一种倾斜传感器&#xff0c;但在书写方面的体验很不错&#xff0c;可以用来写字&…

【算法|前缀和系列No.4】leetcode238. 除自身以外数组的乘积

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【leetcode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…

如何实现前端数据持久化(LocalStorage、IndexedDB等)?

聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…

MySQL InnoDB引擎深入学习的一天(InnoDB架构 + 事务底层原理 + MVCC)

目录 逻辑存储引擎 架构 概述 内存架构 Buffer Pool Change Buffe Adaptive Hash Index Log Buffer 磁盘结构 System Tablespace File-Per-Table Tablespaces General Tablespaces Undo Tablespaces Temporary Tablespaces Doublewrite Buffer Files Redo Log 后台线程 事务原…

Hadoop 配置 Kerberos 认证

1、安装 Kerberos 服务器和客户端 1.1 规划 服务端&#xff1a; bigdata3 客户端&#xff08;Hadoop集群&#xff09;&#xff1a; bigdata0 bigdata1 bigdata2 192.168.50.7 bigdata0.example.com bigdata0 192.168.50.8 bigdata1.example.com bigdata1 192.168.50.9 b…

4.Python-用Python,Ajax实现MySQL数据库的新增数据

题记 用python&#xff0c;ajax实现mysql数据库的新增数据。以下是一个简单的实例和操作过程。 安装flask模块 pip install flask 安装mysql.connector模块 pip install mysql-connector-python 编写app.py文件 app.py文件如下&#xff1a; 块引用可能显示不完整&#x…

第15章 SpringBoot

所有的流程逻辑原理都是针对2.3.2.RELEASE版本 15.1 谈谈你对微服务架构演进的理解 难度:★ 重点:★ 白话解析 还是串主线,在串主线的过程中发现问题,解决问题。主线的入口:随着业务的逻辑越来越复杂,架构再不断升级演进,先理解架构的演进。 这道题参考了:企业IT架构转…

kantts docker化

kan-tts docker本地化 环境安装 下载docker镜像(python3.8的) registry.cn-hangzhou.aliyuncs.com/modelscope-repo/modelscope:ubuntu20.04-cuda11.8.0-py38-torch2.0.1-tf2.13.0-1.9.2 安装基础模型 pip install modelscope 安装语音模型 pip install "modelscope…

系列八、Redis的事务

一、是什么 可以一次执行多个命令&#xff0c;本质是一组命令的集合。一个事务中的所有命令都会序列化&#xff0c;按顺序地串行化执行而不会被其他命令插入&#xff0c;不允许加塞。 二、能干嘛 一个队列中&#xff0c;一次性、顺序性、排他性的执行一些列命令。 三、怎么玩…

git本地仓库及远端仓库推送【linux】

git本地仓库及远端仓库推送【linux】 一.git上创建仓库二.linux中git三板斧i.检查是否安装gitii.克隆仓库到本地iii.提交到本地仓库iiii.上传到远端仓库 三.其他内容补充git loggit status.gitignore 一.git上创建仓库 已经创建好的可以直接跳到第二步进入到创建仓库界面&…

SpringBoot + 自定义注解 + AOP 高级玩法打造通用开关

前言 最近在工作中迁移代码的时候发现了以前自己写的一个通用开关实现&#xff0c;发现挺不错&#xff0c;特地拿出来分享给大家。 为了有良好的演示效果&#xff0c;我特地重新建了一个项目&#xff0c;把核心代码提炼出来加上了更多注释说明&#xff0c;希望xdm喜欢。 案例 …

SQL注入漏洞

0x01 漏洞介绍 泛微e-office系统是标准、易用、快速部署上线的专业协同OA软件&#xff0c;国内协同OA办公领域领导品牌&#xff0c;致力于为企业用户提供专业OA办公系统、移动OA应用等协同OA整体解决方案。泛微e-office深谙改革之道以迎变革之机&#xff0c;沉心产品研发数十载…

电子笔记真的好用吗?手机上适合记录学习笔记的工具

提及笔记&#xff0c;不少人都会和学习挂钩&#xff0c;的确学习过程中我们经常会遇到很多难题&#xff0c;而经常记录笔记可以有效地帮助大家记住很多知识&#xff0c;而且时常拿出笔记查看一下&#xff0c;可方便巩固过去学习的知识。 手机作为大家日常随身携带的工具&#…

Matlab进阶绘图第31期—桑基图(Sankey Chart)

桑基图&#xff08;Sankey Chart&#xff09;本质为一种流程图&#xff0c;可以很好地展示数据的层次结构以及流量变化。 桑基图主要由节点块与流动路径线组成。 其中&#xff0c;节点块用于表示类别&#xff1b;流动路径线除了可以直观地表示流动的方向&#xff0c;其宽度还…

【EI会议征稿】第九届能源资源与环境工程研究进展国际学术会议(ICAESEE 2023)

第九届能源资源与环境工程研究进展国际学术会议&#xff08;ICAESEE 2023&#xff09; 2023 9th International Conference on Advances in Energy Resources and Environment Engineering 第九届能源资源与环境工程研究进展国际学术会议&#xff08;ICAESEE 2023&#xff09;…