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

每日一题--数组中只出现一次的两个数字

数组中只出现一次的两个数字

    • 题目描述
      • 数据范围
      • 提示
    • 示例
      • 示例1
      • 示例2
    • 题解
      • 解题思路
        • 位运算方法
        • 步骤:
    • 代码实现
    • 代码解析
    • 时间与空间复杂度
    • 按位与操作获取最小位1的原理
    • 为什么选择最低有效的 1 位而不是其他位?

题目描述

一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

数据范围

  • 数组长度:2 ≤ n ≤ 1000
  • 数组元素值:0 < val ≤ 1000000

要求:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

提示

  • 输出时按非降序排列。

示例

示例1

输入:

[1,4,1,6]

返回值:

[4,6]

说明:

  • 返回的结果中较小的数排在前面。

示例2

输入:

[1,2,3,3,2,9]

返回值:

[1,9]

题解

解题思路

本题要求找出数组中出现一次的两个数字。由于数组中只有两个数字出现一次,其他数字都出现了两次。我们可以利用 位运算 来高效求解。

位运算方法
  1. 异或运算:我们可以利用异或(^)的特性来解决这个问题。异或运算有以下特点:

    • a ^ a = 0,即相同的数字异或结果为0;
    • a ^ 0 = a,即任何数字与0异或结果为其本身;
    • 异或运算具有交换律和结合律。
  2. 求解步骤

    • 将数组中的所有数字进行异或。由于其他数字都出现了两次,它们的异或结果为0,最后剩下的就是两个只出现一次的数字的异或结果。
    • 假设这两个只出现一次的数字为 xy,那么 x ^ y 就是一个非0的值。我们可以根据 x ^ y 的二进制表示找到 xy 的不同位。
    • 通过分组操作,将所有数字根据该位进行分组,这样就可以分别找到 xy
步骤:
  1. 对数组中的所有元素进行异或,得到 xor
  2. 找到 xor 中某一位的为1的位置(即 xor 中第一个为1的位置),这表示 xy 在这一位上不同。
  3. 根据该位置将所有数字分为两组,分别对每组中的数字异或,得到的结果即为 xy

代码实现

/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param nums int整型一维数组* @param numsLen int nums数组长度* @return int整型一维数组* @return int* returnSize 返回数组行数*/
int* FindNumsAppearOnce(int* nums, int numsLen, int* returnSize ) {*returnSize = 2;int* result = (int*)malloc(*returnSize * sizeof(int));int xor = 0;for (int i = 0; i < numsLen; i++) {xor ^= nums[i];}int right1 = xor &(-xor);*result = 0;  // 初始化结果数组*(result + 1) = 0;for (int i = 0; i < numsLen; i++) {if ((nums[i]&right1) !=0)*result ^= nums[i];else*(result + 1) ^= nums[i];}if(*(result + 1)<*result){*(result + 1)^=*result;*result^=*(result + 1);*(result + 1)^=*result;}return result;// write code here
}

代码解析

  1. 第一步:我们通过对所有数字进行异或得到 xorResult,这个值是两个只出现一次的数字的异或结果。

  2. 第二步:我们找到 xorResult 中最低为1的位。通过 xorResult & (-xorResult) 操作,即xorResult & (~xorResult+1) 我们获取到这一位的值。

  3. 第三步:根据该位的值将数组中的元素分为两组:

    • 如果该位为1,则将元素分配到一组(在 num1 中异或);
    • 如果该位为0,则将元素分配到另一组(在 num2 中异或)。
  4. 第四步:异或操作后,num1num2 就分别是我们要找的两个只出现一次的数字。

  5. 返回结果:最后,我们返回按非降序排列的两个数字。

时间与空间复杂度

  • 时间复杂度O(n),我们遍历了一遍数组进行异或运算。
  • 空间复杂度O(1),我们只用了常数空间来存储临时变量。
    要理解为什么 xorResult & (-xorResult)(或者等价的 xorResult & (~xorResult + 1)) 能得到 xorResult 中最低有效的 1 位的值,我们需要从二进制和补码的角度来分析。

按位与操作获取最小位1的原理

xorResult & (-xorResult) 的效果依赖于补码的特性。我们逐步解析这个过程:

  • xorResult 中最低有效的 1 位前的所有位都是 0 或者 1,而这个最低有效的 1 位后的所有位都应该是 0
  • -xorResultxorResult 取反再加 1 的结果,它和 xorResult 在最低有效 1 位之前的二进制位完全相反,且在最低有效 1 位后面与 xorResult 的二进制位相同。

让我们举一个具体的例子,假设 xorResult = 12,其二进制表示为:

x o r R e s u l t = 00000000000000000000000000001100 xorResult = 00000000 00000000 00000000 00001100 xorResult=00000000000000000000000000001100

-xorResult(即 ~xorResult + 1)为:

− x o r R e s u l t = 11111111111111111111111111110100 -xorResult = 11111111 11111111 11111111 11110100 xorResult=11111111111111111111111111110100

然后进行按位与操作:

x o r R e s u l t & ( − x o r R e s u l t ) = 00000000000000000000000000001100 & 11111111111111111111111111110100 = 00000000000000000000000000000100 xorResult \& (-xorResult) = 00000000 00000000 00000000 00001100 \& 11111111 11111111 11111111 11110100 = 00000000 00000000 00000000 00000100 xorResult&(xorResult)=00000000000000000000000000001100&11111111111111111111111111110100=00000000000000000000000000000100

得到的结果是:

00000000000000000000000000000100 00000000 00000000 00000000 00000100 00000000000000000000000000000100

这个结果是 4,也就是最低有效 1 位的值。

为什么选择最低有效的 1 位而不是其他位?

最后得到的xor是所有的异或位,a^b,如果最低为为1,说名最低有效的 1 位,是因为它是异或结果中最早出现的差异位,它能够最早地分割数组,使得我们能更快地定位到这两个不同的数字。分割成两组,一组为这位是1和多个出现两次的数,然后,一组为这位是0和多个出现两次的数,多个出现两次的数异或后为0。所以解决

相关文章:

每日一题--数组中只出现一次的两个数字

数组中只出现一次的两个数字 题目描述数据范围提示 示例示例1示例2 题解解题思路位运算方法步骤&#xff1a; 代码实现代码解析时间与空间复杂度按位与操作获取最小位1的原理为什么选择最低有效的 1 位而不是其他位&#xff1f; 题目描述 一个整型数组里除了两个数字只出现一次…...

【数据】数据领域常用名词解释(第一批40个)+ 例子

导读&#xff1a;这些名词解释是基于数据领域的基本原理、技术方法、行业实践以及政策规范等多方面因素综合制定的&#xff0c;旨在为社会各界提供统一、权威的参考标准&#xff0c;推动数据领域的健康有序发展。 目录 数据 原始数据 数据资源 数据要素 数据产品和服务 数…...

Java | RESTful 接口规范

关注&#xff1a;CodingTechWork 引言 作为一名程序员&#xff0c;制定清晰、一致且高效的 RESTful 接口规范对于团队的开发效率和项目的长期维护至关重要。本文将详细介绍 RESTful 接口的设计理念、请求方法分类、核心规范&#xff0c;以及正确和错误的示例&#xff0c;帮助团…...

Baklib优化数字化内容管理用科技提升商业效率与增值潜力

内容概要 在当今数字化迅速发展的时代&#xff0c;数字化内容管理已成为企业提升竞争力的重要手段。Baklib作为一款强大的智能优化内容管理系统&#xff0c;通过先进的科技手段&#xff0c;帮助企业在内容管理和数据整合方面实现高效运作。Baklib 是什么类型的工具&#xff0c…...

【AI日记】25.02.09

【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】【AI日记】【读书与思考】【AI应用】 探索 探索 AI 应用 读书 书名&#xff1a;理解公司&#xff1a;产权、激励与治理作者&#xff1a;张维迎 律己 探索&#xff1a;8 小时作息&#xff1a;2:00-10:00短视频娱乐&am…...

Chrome浏览器原理及优化

1. 相关面试题 1.1. 请说说从输入 URL 到页面渲染完成的全过程 1. 输入URL,用户在浏览器的地址栏输入一个URL,并按下回车键; 2. DNS解析; 浏览器需要将域名转换为服务器的IP地址,以建立连接。 (1). 如果浏览器缓存、操作系统缓存或路由器缓存中已有该域名的IP地址,…...

2025_2_9 C语言中队列

1.队列&#xff08;先进先出&#xff09; 队列也是一种受限制的线性结构 它只能在一端添加元素&#xff0c;在另一端访问&#xff0c;删除元素 &#xff08;队首插入&#xff0c;队尾删除&#xff09; 因为链表实现没有数组实现快&#xff0c;所以队列大多数是用数组实现的 q…...

[图文]DeepSeek能做对《软件方法》的测试题吗?

目前为止&#xff0c;我已经针对《软件方法》涉及的知识点出了几百道选择题&#xff0c;我们来看一下DeepSeek能不能做对这些题。 在选择题目时&#xff0c;我刻意向后兼容&#xff0c;选择只要受过严谨的软件开发方法学训练&#xff0c;即使没听说过《软件方法》也应该能通过…...

推荐个Deepseek网站

这几天有用到Deepseek&#xff0c;但是官网老时崩溃&#xff0c;硅基流动这个网站感觉还可以用&#xff0c;赠送了十多块钱&#xff0c;用完要收费&#xff0c;但比较便宜&#xff0c;可以接受。 https://siliconflow.cn/zh-cn/models 这里可以设置给模型添加固定的标签需求...

【Linux开发工具】C/C++ 在Linux下的编译器-gcc/g++

目录 一、前言 二、gcc/g的使用 三、程序翻译的四个阶段 1.预处理 2.编译 3.汇编 4.链接 四、动静态库 1.库函数的命名和分类 2. 动静态库的区别 一、前言 学习了vim的使用方法后&#xff0c;我们就可以高效编辑文本文件了&#xff0c;但vim并不像vs一样编辑好.c文件…...

hmi界面:工业设计风格如何识别,有什么应用场景。

一、工业设计风格在 HMI 界面中的视觉特征 &#xff08;一&#xff09;简洁的布局 功能分区明确 工业设计风格的 HMI 界面往往将不同的功能模块进行清晰的分区&#xff0c;每个区域都有明确的用途。例如&#xff0c;操作区、显示区、状态区等划分一目了然&#xff0c;用户可以…...

NIO三大组件

文章目录 概述Channel & BufferSelector服务器设计历史演化多线程版设计线程池版设计selector 版设计 概述 NIO的意思是 non-blocking io 非阻塞 IO 。NIO中存在3大组件&#xff1a;Channel 、 Buffer 、Selector Channel & Buffer channel &#xff08;中文 管道的…...

pytest.fixture

pytest.fixture 是 pytest 测试框架中的一个非常强大的功能,它允许你在测试函数运行前后执行一些设置或清理代码。以下是关于 pytest.fixture 的详细介绍: 一、定义与用途 pytest.fixture 是一个装饰器,用于标记一个函数为 fixture。Fixture 函数中的代码可以在测试函数运…...

MHTML文件如何在前端页面展示

MHTML文件如何在前端页面展示 需求背景&#xff1a; 目前在给证券公司做项目&#xff0c;但是在使用新系统的过程中&#xff0c;甲方还希望之前之前系统的历史记录可以看到。 最初制定的计划是项目组里面做数据的把原系统页面爬取下来&#xff0c;转成图片&#xff0c;直接给…...

学习笔记:在华为云ModelArts上运行MindSpore扩散模型教程

目录 一、背景与目的 二、环境搭建 三、模型原理学习 1. 类定义与初始化 2. 初始卷积层 3. 时间嵌入模块 4. 下采样模块 5. 中间模块 6. 上采样模块 7. 最终卷积层 8. 前向传播 9. 关键点总结 四、代码实现与运行 五、遇到的问题及解决方法 六、总结与展望 教程来源&#xff1a…...

使用sharding-jdbc实现读写分离

简介 读写分离是一种数据库架构设计的模式&#xff0c;主要用于提高数据库的性能和可扩展性。它将数据库的读取操作和写入操作分离到不同的数据库实例上&#xff0c;从而优化系统的负载和响应速度。 实现前提是需要进行主从复制&#xff08;数据层面的分离&#xff09; 实现…...

“图像识别分割算法:解锁视觉智能的关键技术

嘿&#xff0c;各位朋友&#xff01;今天咱们来聊聊图像识别分割算法。这可是计算机视觉领域里特别厉害的一项技术&#xff0c;简单来说&#xff0c;它能让机器“看懂”图像中的不同部分&#xff0c;并把它们精准地分出来。想象一下&#xff0c;机器不仅能识别出图里有猫还是狗…...

【Go语言快速上手】第二部分:Go语言进阶

文章目录 并发编程goroutine&#xff1a;创建和调度 goroutinechannel&#xff1a;无缓冲 channel、有缓冲 channel、select 语句无缓冲 channel有缓冲 channelselect 语句 sync 包&#xff1a;Mutex、RWMutex、WaitGroup 等同步原语Mutex&#xff1a;互斥锁RWMutex&#xff1a…...

GRN前沿:GRETA:从多模式单细胞数据推断基因调控网络方法的比较与评价

1.论文原名&#xff1a;Comparison and evaluation of methods to infer gene regulatory networks frommultimodal single-cell data 2.发表日期&#xff1a;20254.12.21 摘要&#xff1a; 细胞通过基因表达调节其功能&#xff0c;由转录因子和其他调节机制的复杂相互作用驱…...

python基础入门:4.4模块与包管理

Python模块与包管理完全指南&#xff1a;构建可维护的代码结构 # 示例项目结构 """ my_package/ ├── __init__.py ├── core/ │ ├── __init__.py │ ├── utils.py │ └── calculator.py ├── data/ │ └── config.json └── tes…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...