Leetcode 只出现一次的元素

在这里插入图片描述
题目要求我们找到数组中只出现了一次的元素,而其他元素都出现了两次。

解题思路

我们可以使用位运算中的异或操作(XOR)。异或操作有以下两个特性:

  1. 相同的两个数字异或结果为0,例如:a ^ a = 0
  2. 任意数字与0异或结果是其本身,例如:a ^ 0 = a

异或的规则是:

  • 1 ^ 1 = 0
  • 0 ^ 0 = 0
  • 1 ^ 0 = 1
  • 0 ^ 1 = 1

异或具有交换律和结合律 !! 所以,如果那些2次出现的元素并不是成相邻重复出现的,我们根据异或操作的交换律可以交换成相邻重复出现的,然后根据结合律将2个相同的重复元素先进行异或,最后所有重复的元素都变成0,只剩下0和出现一次的元素进行异或得到出现一次的元素本身。

是的!你已经完全理解了异或操作在这个算法中的工作原理。

异或操作的核心要点:

  1. 交换律:你可以交换操作数的顺序,异或操作的结果不受顺序影响。因此,即使那些两次出现的数字在数组中不是相邻的,也可以通过交换律想象它们是相邻的。

    举例:在 [4, 1, 2, 1, 2] 中,虽然两个 1 和两个 2 并不相邻,但我们可以通过交换律把它们放在一起进行异或:
    4 ⊕ 1 ⊕ 2 ⊕ 1 ⊕ 2 ≡ 4 ⊕ ( 1 ⊕ 1 ) ⊕ ( 2 ⊕ 2 ) 4 \oplus 1 \oplus 2 \oplus 1 \oplus 2 \equiv 4 \oplus (1 \oplus 1) \oplus (2 \oplus 2) 412124(11)(22)

  2. 结合律:结合律允许我们重新组合操作数。结合律可以让我们先把成对的数字组合在一起进行异或运算。

    举例:根据结合律,我们可以先对相同的数字 12 进行异或:
    4 ⊕ ( 1 ⊕ 1 ) ⊕ ( 2 ⊕ 2 ) 4 \oplus (1 \oplus 1) \oplus (2 \oplus 2) 4(11)(22)

  3. 相同数字的异或结果为 0:根据异或的性质,两个相同的数字异或结果为 0。因此:
    4 ⊕ ( 1 ⊕ 1 ) ⊕ ( 2 ⊕ 2 ) = 4 ⊕ 0 ⊕ 0 4 \oplus (1 \oplus 1) \oplus (2 \oplus 2) = 4 \oplus 0 \oplus 0 4(11)(22)=400

  4. 任意数字与 0 异或结果为自身:最后,剩下的结果就是 4,因为 4 ⊕ \oplus 0 = 4。

总结:

  • 交换律结合律 使我们能够无视数组中数字的顺序和排列。
  • 相同的数字异或为 0,因此成对的数字会在异或操作中互相抵消。
  • 最终,所有成对出现的数字都变成了 0,只出现一次的数字留下来,它与 0 异或后结果就是该数字本身。

因此,不管数组中那些成对的数字如何排列,最终只出现一次的那个数字会被正确地找到。这也是为什么这种算法在处理这个问题时如此高效且简单。
在异或操作中,一个数字与另一个数字进行两次异或会恢复原始数字。这是异或操作的一个重要性质,也是这个算法正确性的关键

为什么相同数字两次异或会恢复原始数字?

当你对一个数字进行两次异或操作时,由于异或具有 交换律和结合律,两个相同的数字异或会抵消为0,剩下的就是其他数字的异或结果。

假设我们有两个相同的数字 A A A,异或两次:

  1. r e s u l t = r e s u l t ⊕ A result = result \oplus A result=resultA (此时 result 中存储了第一次与 A A A 的异或结果)
  2. r e s u l t = r e s u l t ⊕ A result = result \oplus A result=resultA (再次异或相同的 A A A,则结果会回到原来的 result

具体过程:

  • 第一次异或:result = result ^ A
  • 第二次异或:result = (result ^ A) ^ A
    • 根据异或的结合律,我们可以把式子重新组合:
    • result = result ^ (A ^ A)
    • 由于 A ⊕ A = 0 A \oplus A = 0 AA=0,最终结果为:result = result ^ 0 = result

这样,经过两次异或,原本的 result 被还原,而成对出现的数字最终会被抵消。

总结:

  • 数字与自身异或两次会恢复原始值,这是因为异或的 交换律和结合律
  • 在这种情况下,所有成对出现的数字会被互相抵消为0,只出现一次的数字则会留下。
  • 这就是为什么这个算法能够有效地找到数组中只出现一次的元素。

因此,假设数组中除了一个元素只出现一次外,其他元素都出现两次,我们可以通过对数组中所有元素进行异或操作,最终结果就是那个只出现一次的数字。

C++代码:

class Solution {
public:int singleNumber(vector<int>& nums) {int result = 0;for (int num : nums) {result = result ^ num;  // 使用异或运算}return result;}
};

代码解释:

  • 初始化一个变量 result 为0。
  • 遍历数组 nums,对数组中的每个元素进行异或操作,最终的结果就是只出现一次的元素。
  • 返回 result

这个算法的时间复杂度是 O(n),空间复杂度是 O(1),符合题目的要求。

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

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

相关文章

Android12——Launcher3文件夹布局修改调整

文章声明&#xff1a;本文是笔者参考良心大佬作品后结合实际需求进行相应的定制&#xff0c;本篇主要是笔者记录一次解析bug笔记&#xff0c;文中可能会引用大佬文章中的部分图片在此声明&#xff0c;并非盈利目的&#xff0c;如涉嫌侵权请私信&#xff0c;谢谢&#xff01; 大…

基于亲和性的 GPU 容器绑核策略 Copy

1.引言 在高性能计算和大规模并行任务处理中&#xff0c;GPU已经成为不可或缺的加速器。为了充分发挥GPU的计算能力&#xff0c;通过合理分配CPU核与GPU的绑定来优化CPU和GPU的关系至关重要。我们将探讨socket和NUMA&#xff08;非统一内存访问&#xff09;的概念&#xff0c;并…

力扣 — — 2555. 两个线段获得的最多奖品

力扣 — — 2555. 两个线段获得的最多奖品 一、题目描述 题目大意&#xff1a;给定一个数组prizePositions&#xff0c;数组中的值表示的是奖品的位置&#xff0c;每一个位置可以有多个奖品&#xff0c;并且设定一个线段的长度 K K K&#xff0c;要求从所有奖品位置中选择两个…

springboot 整合quartz定时任务

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、pom的配置1.加注解二、使用方法1.工程图2.创建工具类三、controller 实现前言 提示:这里可以添加本文要记录的大概内容: 提示:以下是本篇文章正文内容,下面案例可供参考 一、pom的配…

【RabbitMQ】工作模式

工作模式概述 简单模式 简单模式中只存在一个生产者&#xff0c;只存在一个消费者。生产者生产消息&#xff0c;消费者消费消息。消息只能被消费一次&#xff0c;也称为点对点模式。 简单模式适合在消息只能被单个消费者处理的场景下存在。 工作队列模式&#xff08;Work Qu…

Redisson分布式锁实现及原理详解

随着技术快速发展&#xff0c;数据规模增大&#xff0c;分布式系统越来越普及&#xff0c;一个应用往往会部署在多台机器上&#xff08;多节点&#xff09;&#xff0c;在有些场景中&#xff0c;为了保证数据不重复&#xff0c;要求在同一时刻&#xff0c;同一任务只在一个节点…

浏览器中的JavaScript核心BOM(浏览器对象模型)重点掌握对象之History对象的属性与方法

History对象是用来把网页浏览历史用类似栈的方式进行表示。 这定义听起来非常的抽象&#xff0c;其实History对象的作用就跟浏览器的前进和后退很像&#xff0c;我们来用几幅图来理解一下。首先我们先回顾一下浏览器的返回上一个页面 和 跳转到下一个页面 这两个功能。 就类似…

JDBC使用

7.2 创建JDBC应用 7.2.1 创建JDBC应用程序的步骤 使用JDBC操作数据库中的数据包括6个基本操作步骤&#xff1a; &#xff08;1&#xff09;载入JDBC驱动程序&#xff1a; 首先要在应用程序中加载驱动程序driver&#xff0c;使用Class.forName()方法加载特定的驱动程序&#xf…

【题解单调队列优化dp】划分

划分 分析&#xff1a; 首先&#xff0c;我们目光着眼于部分分 我们尝试用 O ( n 3 ) O(n^3) O(n3)的朴素dp去解决这个问题 f [ i ] [ j ] 表示划分到第 i 个位置&#xff0c;且上一个位置是 j 的最小运行时间是多少 f[i][j]表示划分到第i个位置&#xff0c;且上一个位置是j的…

erlang学习: Mnesia Erlang数据库3

Mnesia数据库删除实现和事务处理 -module(test_mnesia). -include_lib("stdlib/include/qlc.hrl").-record(shop, {item, quantity, cost}). %% API -export([insert/3, select/0, select/1, delete/1, transaction/1,start/0, do_this_once/0]). start() ->mnes…

自然语言处理系列六十九》搜索引擎项目实战》搜索框架技术选型

注&#xff1a;此文章内容均节选自充电了么创始人&#xff0c;CEO兼CTO陈敬雷老师的新书《自然语言处理原理与实战》&#xff08;人工智能科学与技术丛书&#xff09;【陈敬雷编著】【清华大学出版社】 文章目录 自然语言处理系列六十九搜索引擎项目实战》搜索框架技术选型搜索…

(k8s)kubernetes 挂载 minio csi 的方式

一、安装Minio&#xff08;Minio分布式集群搭建部署_minio集群最少几台-CSDN博客&#xff09; 生成accessKeyID和secretAccessKey&#xff1a; 二、安装csi-s3插件(在k8s集群上) 首先我们把插件的yaml文件都下载下来&#xff0c;为了保证版本测试的一致性&#xff0c;我们下载…

828华为云征文|基于华为云Flexus云服务器X搭建jumpserver堡垒机软件

文章目录 ❀前言❀jumpserver堡垒机概述❀环境准备❀部署说明❀在线安装❀浏览器访问❀资产添加❀资产授权❀资产登录❀总结 ❀前言 近期华为云推出了最新的华为云Flexus云服务器X&#xff0c;这款云主机在算柔性算力做出了重大变革。华为云Flexus云服务器X基于擎天QingTian架…

QT设置闹钟超时播报

头文件 #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include<QTimerEvent> #include<QTime> #include<QTextToSpeech>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic…

一个基于Spring Boot 3、Vue 3 和 Element-Plus 的中后台管理框架,流畅、直观且功能强大

前言 当前市面上的中后台管理系统虽然种类繁多&#xff0c;但在实际使用中仍存在不少痛点&#xff0c;比如技术栈陈旧、性能低下、扩展性差等问题。开发者们常常需要花费大量的时间和精力去处理这些问题&#xff0c;而不是专注于业务逻辑本身。 那么&#xff0c;有没有一个框…

计算赎金信

给你两个字符串&#xff1a;ransomNote 和 magazine &#xff0c;判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以&#xff0c;返回 true &#xff1b;否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。 示例 1&#xff1a; 输入&#xff…

使用3DUNet训练自己的数据集(pytorch)— 医疗影像分割

代码:lee-zq/3DUNet-Pytorch: 3DUNet implemented with pytorch (github.com) 文章<cicek16miccai.pdf (uni-freiburg.de)3D U-Net: Learning Dense Volumetric Segmentation

HarmonyOS学习(十)——网络编程

文章目录 1、通过HTTP请求网络2、Web组件2.1、加载本地网页2.2、加载在线网页2.3、网页缩放2.4、文本缩放2.5、web组件事件以及状态说明2.6、处理页面导航 1、通过HTTP请求网络 官方API文档地址&#xff1a;HTTP数据请求-Network Kit数据传输能力-Network Kit&#xff08;网络…

Linux 下 C/C++ 程序编译的过程

目录 一、GCC 工具链二、编译过程1、预处理2、编译3、汇编4、链接 本文将介绍如何将 C/C 语言编写的程序转换成为处理器能够执行的二进制代码的过程&#xff0c;包括四个步骤&#xff1a;预处理&#xff08;Preprocessing&#xff09;编译&#xff08;Compilation&#xff09;汇…

Qt_自定义信号

目录 1、自定义信号的规定 2、创建自定义信号 3、带参数的信号与槽 4、一个信号连接多个槽 5、信号与槽的断开 结语 前言&#xff1a; 虽然Qt已经内置了大量的信号&#xff0c;并且这些信号能够满足大部分的开发场景&#xff0c;但是Qt仍然允许开发者自定义信号&#…