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

LeetCode算法位运算—只出现一次的数字

目录

136. 只出现一次的数字 - 力扣(LeetCode)

解题思路:

代码:

运行结果:

补充

 异或的重要性质


136. 只出现一次的数字 - 力扣(LeetCode)

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

示例 1 :

输入:nums = [2,2,1]
输出:1

示例 2 :

输入:nums = [4,1,2,1,2]
输出:4

示例 3 :

输入:nums = [1]
输出:1

提示:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 除了某个元素只出现一次以外,其余每个元素均出现两次。

解题思路:

异或运算(^)的性质:

  • 异或运算满足交换律和结合律,即a^b^c = a^(b^c)。
  • 对于任何数x,x^x=0,即一个数与自己异或的结果为0。
  • 对于任何数x,x^0=x,即一个数与0异或的结果为它本身。

考虑到这些性质,让我们看一下代码的执行过程:

  1. 初始化变量a为0。
  2. 遍历数组nums中的每个元素:
    • 将a与当前元素进行异或操作,即a^=nums[i]。
    • 异或操作会将出现两次的数字消除,因为两个相同的数字异或的结果为0。
    • 异或操作会将只出现一次的数字留下,因为任何数字与0异或的结果为它本身。
    • 最终,a将保留只出现一次的数字。
  3. 返回变量a作为结果。

现在,让我们通过一个案例来解析这段代码:

假设输入数组nums为[2, 4, 2, 1, 4],其中只有数字1只出现一次,其他数字都出现了两次。

执行过程如下:

  1. 初始化变量a为0。
  2. 遍历数组nums:
    • 第一次循环:a^=2,a的值变为2。
    • 第二次循环:a^=4,a的值变为6。
    • 第三次循环:a^=2,a的值变为4。
    • 第四次循环:a^=1,a的值变为5。
    • 第五次循环:a^=4,a的值变为1。
  3. 返回a的值1作为结果。

代码:

class Solution {public int singleNumber(int[] nums) {int a=0;for(int i=0;i<nums.length;i++){a^=nums[i];}return a;}
}

运行结果:

补充

 异或的重要性质

  1. 结合律:异或运算满足结合律,即对于任意三个数a、b和c,满足 (a ^ b) ^ c = a ^ (b ^ c)。

  2. 自反性:任何数与自身进行异或运算的结果为0,即 a ^ a = 0。这是因为异或运算可以看作是"无进位相加",而相同的位进行异或运算结果为0。

  3. 零元素:0是异或运算的零元素,即对于任何数a,满足 a ^ 0 = a。这是因为异或运算中,任何数与0进行异或运算结果为它本身。

  4. 逆元素:每个数在异或运算中都有逆元素,即对于任何数a,存在一个数b,满足 a ^ b = 0。这意味着可以通过异或运算来撤销一个数的影响。

  5. 消除相同元素:当数组中有成对出现的相同元素时,对整个数组进行异或运算,最终结果为0。这是因为相同元素异或的结果为0,而异或运算满足交换律和结合律。

这些性质使得异或运算在很多场景下非常有用,例如查找只出现一次的数字、判断两个数是否相等、交换两个变量的值等。通过利用这些性质,可以简化问题的处理和求解。

相关文章:

LeetCode算法位运算—只出现一次的数字

目录 136. 只出现一次的数字 - 力扣&#xff08;LeetCode&#xff09; 解题思路&#xff1a; 代码&#xff1a; 运行结果&#xff1a; 补充 异或的重要性质 136. 只出现一次的数字 - 力扣&#xff08;LeetCode&#xff09; 给你一个 非空 整数数组 nums &#xff0c;除了某…...

vcpkg manifest 的使用

最近项目上要使用 CMakeLists 管理&#xff0c;由于 Windows 版本有依赖到 vcpkg 提供的库&#xff0c;所以需要使用 vcpkg manifest 来统一设置库的版本&#xff0c;方便后续维护 推荐一个文章&#xff0c;介绍的可以说是非常全面了 VCPKG 特性 - Versioning 不过里面也有一些…...

选择什么电容笔比较好?平板手写笔推荐

由于苹果Pencil的热销&#xff0c;让华国内市场上&#xff0c;也出现了不少的平替式电容笔&#xff0c;这些产品&#xff0c;有好有坏&#xff0c;价格也很公道。不过&#xff0c;也有很多产品的价格都很平价。我是一个拥有多年经验的数码发烧友&#xff0c;在前几年就开始用上…...

pdf转二维码怎么做?pdf二维码制作简单技巧

pdf是一种很常见的文件储存格式&#xff0c;一般通知、发票、简历都会保存为这种格式来使用&#xff0c;那么需要将pdf格式文件做成二维码&#xff0c;该用什么方式来制作呢&#xff1f;下面给大家分享一个pdf转二维码的在线工具&#xff0c;可以通过上传文件一键生成二维码&am…...

【CANoe】TX Self-ACK自应答配置与CPAL实现

一、引言 在测试CAN&CANFD通信或者网络管理的时候&#xff0c;我们经常遇到使用报文&#xff08;网络管理报文或者通信报文&#xff09;唤醒被测件这个测试点&#xff0c;如果测试比较多的情况下&#xff0c;我们就会发现&#xff0c;如果CANoe没有接被测件或者被测件没有…...

(Python)MATLAB mat矩阵和Python npy矩阵转换

Python np.ndarray矩阵转换为MATLAB mat文件 import numpy as npimport scipy.io as iomat_path mat_save_pathmat np.zeros([6, 128])io.savemat(mat_path, {name: mat})Python读取MATLAB mat文件 import numpy as np from scipy import iomat io.loadmat(your_mat_file.…...

Flink1.14 SourceReader概念入门讲解与源码解析 (三)

目录 SourceReader 概念 SourceReader 源码方法 void start(); InputStatus pollNext(ReaderOutput output) throws Exception; List snapshotState(long checkpointId); CompletableFuture isAvailable(); void addSplits(List splits); 参考 SourceReader 概念 Sour…...

PS运行中缺失d3dcompiler_47.dll问题的5个有效修复方法总结

在使用ps作图的时候&#xff0c;我们有时会遇到一些问题&#xff0c;其中之一就是“PS运行中缺失d3dcompiler_47.dll”的问题。这个问题可能会导致PS无法正常运行&#xff0c;“d3dcompiler_47.dll”。这是一个动态链接库文件&#xff0c;它是DirectX的一部分&#xff0c;主要负…...

【MATLAB-Retinex图像增强算法的去雾技术】

续&#xff1a;【MATLAB-基于直方图优化的图像去雾技术】 【MATLAB-Retinex图像增强算法的去雾技术】 1 原图2 MATLAB实现代码3 结果图示 参考书籍&#xff1a;计算机视觉与深度学习实战:以MATLAB、Python为工具&#xff0c; 主编&#xff1a;刘衍琦, 詹福宇&#xff0c; 王德建…...

使用 2 个 HSplitView 在 swiftUI 中创建一个 3 窗格界面

Pet*_*ter 8 嗯&#xff0c;我会的。在断断续续地挣扎了几个星期之后&#xff0c;在我问这个问题一个小时后&#xff0c;我似乎解决了它&#xff01;只需将第二个 HSplitView 的 layoutPriority 设置为 1&#xff0c;并将中心视图也设置为 1。当你想到它时是有道理的&#xff1…...

【C++ 操作符重载:定制自己的运算符行为】

在C编程中&#xff0c;操作符重载是一项强大的特性&#xff0c;它允许程序员定制内置运算符的行为&#xff0c;使它们适用于用户自定义的数据类型。这篇博客将介绍什么是操作符重载&#xff0c;如何使用它&#xff0c;以及一些最佳实践。 什么是操作符重载&#xff1f; 操作符…...

Android Fragment 基本概念和基本使用

Android Fragment 基本概念和基本使用 一、基本概念 Fragment&#xff0c;简称碎片&#xff0c;是Android 3.0&#xff08;API 11&#xff09;提出的&#xff0c;为了兼容低版本&#xff0c;support-v4库中也开发了一套Fragment API&#xff0c;最低兼容Android 1.6。 过去s…...

xml schema中的all元素

说明 xml schema中的all元素表示其中的子元素可以按照任何顺序出现&#xff0c;每个元素可以出现0次或者1次。 https://www.w3.org/TR/xmlschema-1/#element-all maxOccurs的默认值是1&#xff0c;minOccurs 的默认值是1。 举例 <element name"TradePriceRequest&…...

Java8实战-总结42

Java8实战-总结42 用Optional取代null应用 Optional 的几种模式默认行为及解引用 Optional 对象两个 Optional 对象的组合使用 filter 剔除特定的值 用Optional取代null 应用 Optional 的几种模式 默认行为及解引用 Optional 对象 采用orElse方法读取这个变量的值&#xff0…...

实现日期间的运算——C++

&#x1f636;‍&#x1f32b;️Take your time ! &#x1f636;‍&#x1f32b;️ &#x1f4a5;个人主页&#xff1a;&#x1f525;&#x1f525;&#x1f525;大魔王&#x1f525;&#x1f525;&#x1f525; &#x1f4a5;代码仓库&#xff1a;&#x1f525;&#x1f525;魔…...

云上攻防-云原生篇K8s安全Config泄漏Etcd存储Dashboard鉴权Proxy暴露

文章目录 云原生-K8s安全-etcd未授权访问云原生-K8s安全-Dashboard未授权访问云原生-K8s安全-Configfile鉴权文件泄漏云原生-K8s安全-Kubectl Proxy不安全配置 云原生-K8s安全-etcd未授权访问 攻击2379端口&#xff1a;默认通过证书认证&#xff0c;主要存放节点的数据&#x…...

ChatGPT 的工作原理学习 难以理解 需要先找个容易的课来跟下。

ChatGPT 的工作原理 传统搜超搜引擎原理&#xff1a;蜘蛛抓取和数据收集&#xff0c;用户交互查找。 ChatGPT 的工作原理&#xff1a;数据收集称为预训练&#xff0c;用户响应阶段称为推理。 ChatGPT是一种基于自然语言处理技术的人工智能模型&#xff0c;它的工作原理建立在…...

5.DApp-前端网页怎么连接MetaMask

题记 在前端网页连接metamask&#xff0c;以下是全部操作流程和代码。 编写index.html文件 index.html文件如下&#xff1a; <!DOCTYPE html> <html> <head> <title>My DApp</title> <!--导入用于检测Metamask提供者的JavaScript库--> &l…...

手机应用app打开游戏显示连接服务器失败是什么原因?排查解决方案?

亲爱的同学们&#xff0c;有时候我们在使用手机设备时&#xff0c;可能会遇到一个很头疼的问题——连接服务器失败。这个问题不仅让我们感到困扰&#xff0c;还影响到了我们的用户体验。那么&#xff0c;我们究竟能如何解决这个问题呢&#xff1f;今天&#xff0c;笔者就和大家…...

【Java学习之道】指引篇:从入门到入世

引言 你是否曾为找不到适合自己的Java学习之路而烦恼&#xff1f;是否想摆脱混乱的Java知识体系&#xff0c;找到一条从入门到精通的捷径&#xff1f;来《Java学习之道》吧&#xff0c;本专栏为你量身打造&#xff0c;让我们一起轻松踏上Java学习之旅&#xff01; 第一章、Jav…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

【版本控制】GitHub Desktop 入门教程与开源协作全流程解析

目录 0 引言1 GitHub Desktop 入门教程1.1 安装与基础配置1.2 核心功能使用指南仓库管理日常开发流程分支管理 2 GitHub 开源协作流程详解2.1 Fork & Pull Request 模型2.2 完整协作流程步骤步骤 1: Fork&#xff08;创建个人副本&#xff09;步骤 2: Clone&#xff08;克隆…...

Android Framework预装traceroute执行文件到system/bin下

文章目录 Android SDK中寻找traceroute代码内置traceroute到SDK中traceroute参数说明-I 参数&#xff08;使用 ICMP Echo 请求&#xff09;-T 参数&#xff08;使用 TCP SYN 包&#xff09; 相关文章 Android SDK中寻找traceroute代码 设备使用的是Android 11&#xff0c;在/s…...

【向量库】Weaviate 搜索与索引技术:从基础概念到性能优化

文章目录 零、概述一、搜索技术分类1. 向量搜索&#xff1a;捕捉语义的智能检索2. 关键字搜索&#xff1a;精确匹配的传统方案3. 混合搜索&#xff1a;语义与精确的双重保障 二、向量检索技术分类1. HNSW索引&#xff1a;大规模数据的高效引擎2. Flat索引&#xff1a;小规模数据…...

Redis专题-实战篇一-基于Session和Redis实现登录业务

GitHub项目地址&#xff1a;https://github.com/whltaoin/redisLearningProject_hm-dianping 基于Session实现登录业务功能提交版本码&#xff1a;e34399f 基于Redis实现登录业务提交版本码&#xff1a;60bf740 一、导入黑马点评后端项目 项目架构图 1. 前期阶段2. 后续阶段导…...

Go爬虫开发学习记录

Go爬虫开发学习记录 基础篇&#xff1a;使用net/http库 Go的标准库net/http提供了完善的HTTP客户端功能&#xff0c;是构建爬虫的基石&#xff1a; package mainimport ("fmt""io""net/http" )func fetchPage(url string) string {// 创建自定…...