【算法基础】基于异或的排序、基于异或的经典面试题
文章目录
- 1. 传统交换
- 2. 异或与异或的规律
- 3. 基于异或的排序
- 4. 需要注意的地方
- 5. 经典面试题1
- 5.1 题目
- 5.2 思路
- 5.3 实现
- 6. 经典面试题2
- 6.1 题目
- 6.2 思路
- 6.3 实现
1. 传统交换
传统交换方法如下:
def swap(i, j):tmp = ii = jj = tmp
通过开辟一个额外的变量空间,承载其中的一个数,以实现变量的交换
2. 异或与异或的规律
异或定义很简单,两数相同则为0,两数相异则为1
异或满足的性质包括结合律和交换律:
- 性质1:
0^a=a
(0与任意数结果取决于任意数),a^a=0
(任意数与其自身异或结果为0) - 性质2:
a^b=b^a
(交换律),(a^b)^c=a^(b^c)
(结合律) - 性质3:基于以上两个性质可以推出,多个数进行异或,无论怎样排序,异或的结果不变
3. 基于异或的排序
基于异或排序的方法如下:
def swap2(i, j):i = i ^ jj = i ^ ji = i ^ j
为什么这样的方法能够奏效,可以看下面的例子:假设i=甲,j=乙
经第一句i = i ^ j
后,i=甲^乙,j=乙
经第二句j = i ^ j
后,i=甲^乙,j=(甲^乙)^乙=甲^(乙^乙)=甲^0=甲
(基于性质1和性质2的结合律)
经第三句i = i ^ j
后,i=(甲^乙)^甲=(甲^甲)^乙=0^乙=乙
(基于性质1和性质2)
从而完成两数交换
4. 需要注意的地方
在写排序时候我们通常需要做交换操作,交换数组中的两个数。如选择排序中我们需要将子数组中最小的数与当前第一位数字交换;又如冒泡排序中我们需要通过两两交换来将最大的数交换到子数组的最高位。
但这时候,当i
和j
指向数组的同一个内存区域时,交换会失败! 也就是说我们想要交换arr[i]
和arr[j]
,而此时i==j
时交换会失败,因为当指向同一片内存区域时,代码就类似于变成了:
def swap2(i):i = i ^ ii = i ^ ii = i ^ i
自身与自身的相与结果为0,所以这样的操作会将原本数组中的数抹成0,而不是保留原数!
若只是交换i、j的值(i
和j
不指向同一片内存区域)则可以成功,i
和j
的值相等也不会被抹成0。听到的一个说法是,原理是靠内存地址来异或的。
5. 经典面试题1
5.1 题目
在int [] arr
中,有一种数出现了奇数次,其他数出现了偶数次,请找出这种奇数次的数。
5.2 思路
通过异或解决,因为同样的数与自身相异或结果为0,偶数条件下也为0(异或的性质1);而出现奇数次的数与0相与的结果为数的本身。所以只需要将所有的变量异或上就行了。
5.3 实现
6. 经典面试题2
6.1 题目
在int [] arr
中,有两种数出现了奇数次,其他数出现了偶数次,请找出这两种出现了奇数次的数
6.2 思路
通过5中的题目可以知道,通过将本题arr中所有数异或,得到的结果应该为a_xor_b = a^b
如何从a_xor_b = a^b
中分离出其中的数是值得思考的问题
考虑的方向是,既然a和b是两个不相等的数,那么a^b的结果一定存在1(从二进制上考虑,a^b的二进制中肯定存在1)
那么这个1就可以作为突破的方向,假设我们从a^b中找到第2位上的数为1,则证明a二进制的第2位和b二进制的第2位是不相等的,一个为0,另一个为1(a可能为0/1,b同理)
此时arr
中的数可以分为两类,一类是在第2位上为1的,另一类是在第2位上为0的,而a和b肯定是分属两类
通过将所有第2位上为1的数进行异或,或将所有第2位上为0的数进行异或,得到的肯定是a和b的其中一个。因为a和b分别属于这两个类中出现奇数次的数,其他偶数次的在异或过程中已经消为0了。
找到了其中一个数后,通过将a_xor_b = a^b
再与找到的数(可能是a也可能是b)进行异或,得到的就是另外一个。
6.3 实现
# 在int [] arr中,有两种数出现了奇数次,其他数出现了偶数次,请找出这两种出现了奇数次的数if __name__ == '__main__':arr = [6, 6, 7, 8, 5, 4, 7, 4, 5, 3]print("原数组为:", arr)a_xor_b = 0for num in arr:a_xor_b = a_xor_b ^ numprint("a^b=", a_xor_b)# a_xor_b=a^b,既然a和b是两个不同的数,a_xor_b中一定存在某一位为1right_one = a_xor_b & (~a_xor_b + 1) # 提取出最右侧的1,是常见的操作only_one = 0for num in arr:if num & right_one == right_one:only_one = only_one ^ numprint("其中一个数为:", only_one)print("另一个数为:", a_xor_b ^ only_one)
相关文章:
【算法基础】基于异或的排序、基于异或的经典面试题
文章目录 1. 传统交换2. 异或与异或的规律3. 基于异或的排序4. 需要注意的地方5. 经典面试题15.1 题目5.2 思路5.3 实现 6. 经典面试题26.1 题目6.2 思路6.3 实现 1. 传统交换 传统交换方法如下: def swap(i, j):tmp ii jj tmp通过开辟一个额外的变量空间&…...
HTML2:列表和表格
列表 有序列表 ordered list ol 无序列表 unordered list ul 定义列表 definition list dl 1,有序列表 每条列表前自带一个序号 2,无序列表 每条列表前自带一个小圆点 3,定义列表 注意:dl中放的不是li列表而是dt列表和dd表项 dt代表术语标题 dd代表术语内容 一个…...

用于无人机小型化设计的高精度温补晶振
用于无人机小型化设计的高精度温补晶振:TG2016SMN和TG2520SMN。无人机的发展可以说是非常的迅速,在安防,农业,交通,电力,直播等领域经常能看到无人机大显身手。无人机的应用场最是非常的广泛,功能更强&…...

轨迹规划 | 图解最优控制LQR算法(附ROS C++/Python/Matlab仿真)
目录 0 专栏介绍1 最优控制理论2 线性二次型问题3 LQR的价值迭代推导4 基于差速模型的LQR控制5 仿真实现5.1 ROS C实现5.2 Python实现5.3 Matlab实现 0 专栏介绍 🔥附C/Python/Matlab全套代码🔥课程设计、毕业设计、创新竞赛必备!详细介绍全…...

工业视觉检测
目录 我对工业视觉检测的了解 一、关键组成部分 二、应用场景 三、技术挑战 我对工业视觉检测的了解 工业视觉检测是利用机器视觉技术对产品质量进行自动化检查的过程,它在制造业中扮演着至关重要的角色,用于确保产品质量、提高生产效率、减少人工成…...

wheeltec轮趣ROS教育机器人的网络连接
一、术语解析 宿主机:宿主机是指物理主机,比如用于开发测试的笔记本电脑和台式机电脑。 虚拟机:虚拟机是指安装在宿主机的VMware,推荐在宿主机上安装虚拟机,官方提供虚拟机的镜像以及配套的开发环境。 ROS主机&…...

【Linux ARM 裸机】开发环境搭建
1、Ubuntu 和 Windows 文件互传 使用过程中,要频繁进行 Ubuntu 和 Windows 的文件互传,需要使用 FTP 服务; 1.1、开启 Ubuntu 下的 FTP 服务 //安装 FTP 服务 sudo apt-get install vsftpd //修改配置文件 sudo vi /etc/vsftpd.conf//重启…...

怎么保证缓存与数据库的最终一致性?
目录 零.读数据的标准操作 一.Cache aside Patten--旁路模式 二.Read/Write Through Pattern--读写穿透 三.Write Back Pattern--写回 四.运用canal监听mysql的binlog实现缓存同步 零.读数据的标准操作 这里想说的是不管哪种模式读操作都是一样的,这是一种统一…...

免费SSL通配符证书/SSL泛域名证书获取教程
我们先基本了解什么是SSL证书以及其作用。SSL证书是一种数字证书,它通过为网站提供身份验证和数据加密服务,从而保护网站的用户信息安全。当我们在浏览器的地址栏看到“https”和绿色锁标志时,就表示该网站使用了SSL证书。 那么什么又是通配…...

mysql结构与sql执行流程
Mysql的大体结构 客户端:用于链接mysql的软件 连接池: sql接口: 查询解析器: MySQL连接层 连接层: 应用程序通过接口(如odbc,jdbc)来连接mysql,最先连接处理的是连接层。 连接层…...

vue快速入门(十二)v-key索引标志
注释很详细,直接上代码 新增内容 v-key的使用场景数组筛选器的使用 源码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-…...
智能网联汽车自动驾驶数据记录系统DSSAD数据配置
目录 第一章 数据配置一般要求 第二章 数据配置文件中的文件描述 第三章 数据配置文件中的数据描述 第四章 数据配置文件中的数据字典 表A.1 数据字典格式定义 第一章 数据配置一般要求 数据配置文件数据内容应为可读的十进制数据。 数据配置文件应以文件的形式存储在自动驾驶…...
linux知识点
绝对路径用什么符号表示?当前目录、上层目录用什么表示?主目录用什么表示? 切换目录用什么命令 绝对路径: 如/etc/init.d当前目录和上层目录: ./ …/主目录: ~/切换目录: cd 怎么查看当前进程?…...

微信小程序实现滚动标签
使用scroll-view标签可实现组件滚动标签 1、list中 list.wxml代码如下: <!--pages/list/list.wxml--> <navigation-bartitle"小程序" back"{{false}}"color"black" background"#FFF"></navigation-bar><scroll-…...

大语言模型上下文窗口初探(下)
由于篇幅原因,本文分为上下两篇,上篇主要讲解上下文窗口的概念、在LLM中的重要性,下篇主要讲解长文本能否成为LLM的护城河、国外大厂对长文本的态度。 3、长文本是护城河吗? 毫无疑问,Kimi从一开始就用“长文本”占领…...
Java整合ElasticSearch8.13
1、引入Jar包 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-elasticsearch</artifactId> </dependency> 2、配置ES连接信息 spring:elasticsearch:# 地址uris: http://xxx:9200# 用户…...

2.网络编程-HTTP和HTTPS
目录 HTTP介绍 HTTP协议主要组成部分 GET 和 POST有什么区别 常见的 HTTP 状态码有哪些 http状态码100 HTTP1.1 和 HTTP1.0 的区别有哪些 HTTPS 和 HTTP 的区别是什么 HTTP2 和 HTTP1.1 的区别是什么 HTTP3 和 HTTP2 的区别是什么 HTTPS的请求过程 对称加密和非对称…...

MTK i500p AIoT解决方案
一、方案概述 i500p是一款强大而高效的AIoT平台,专为便携式、家用或商用物联网应用而设计,这些应用通常需要大量的边缘计算,需要强大的多媒体功能和多任务操作系统。该平台集成了Arm Cortex-A73 和 Cortex-A53 的四核集群,工作频…...

ES入门十四:分词器
我们存储到ES中数据大致分为以下两种: 全文本,例如文章内容、通知内容精确值,如实体Id 在对这两类值进行查询的时候,精确值类型会比较它们的二进制,其结果只有相等或者不想等。而对全文本类型进行等值比较是不太实现…...

汇编——SSE打包整数
SSE也可以进行整数向量的加法,示例如下: ;sse_integer.asm extern printfsection .datadummy db 13 align 16pdivector1 dd 1dd 2dd 3dd 4pdivector2 dd 5dd 6dd 7dd 8fmt1 db "Packed Integer Vector 1: %d, %d, %d, %d",…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...

ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...