找到数组中出现一种/两种奇数——异或运算

找到数组中出现一种/两种奇数

题目:一个数组有一种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这个数?

trick

因为异或运算有个特点,满足交换律和结合律,同时有两个重要的特点:
n^n = 0
n^0 = n

异或运算理论上是:相异为1,相同为0,但其实实际应用时最好把异或运算当作无进位加法来看待,这样比较好记忆。

思路

所以。对于该题,所有数字中,只有一种数出现奇数次,而其他数字都是出现的偶数次,所以我们就可以把所有的数都做异或运算,利用n^n = 0的特点,偶数次的必定被异或为0,奇数次的会保留下来,问题就解决了。

// arr中,只有一种数,出现奇数次
public static void printOddTimesNum1(int[] arr){
	int eor = 0;
	for(int i=0;i<arr.length; i++){
		eor ^= arr[i];
	}
	Systom.out.println(eor);
}

题目二:一个数组有两种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这个数?

trick 交换a,b的值

a = a ^ b
b = a ^ b
a = a ^ b

思路

这道题还是用异或来解决,具体怎么做呢?

  1. 首先把全部的数都做一遍异或运算,因为有两种数是奇数,剩下的全是偶数,偶数做异或结果是0,就不用管,所以最后的异或结果是两个奇数的异或,结果为eor,而这两种奇数又不相等(不要杠,杠就是你赢),所以两个奇数的异或结果必定是不等于0的。

  2. 第二步,我们无法直接从异或结果中找出两个奇数,但是,我们可以从抑或结果中获得一些区别的信息,我们从最后的异或结果中取最后一个1(任何一个1都可以,但是取最后一个1有技巧,比较顺手,所以取最后一个1),这里假设是第八位,因为异或结果中的1,必定代表了这两个奇数在第八位有区别,(一个数在第八位是0,一个数在第八位是1),然后就可以把所有的数分成两类,一类在第八位是1的,一类在第八位是0的。在这里插入图片描述

  3. 我们在用异或结果err和第八位是1的做异或(第八位是0的碰都不要碰),而第八位是1的出现偶数次的依然不会受到干扰,异或结果依然还是0,只有a/b会被这一次的异或结果抓到,结果为eor1,这样我们就找到了第一个奇数,然后在让eor和eor1做异或,就得到了第二个奇数。

  4. 其实这道题目的解法就是来自于上面的trick,不过加入了一些偶数个的干扰数,因为偶数个异或结果为0,丝毫不影响。

// arr中,有两种数,出现奇次数
public static void printOddTimesNum2(int[] arr){
	int eor = 0;
	for(int i=0;i<arr.length;i++){
		eor ^= arr[i];
	}
	
	// eor = a^b
	// eor != 0
	// eor必然有一个位置上是1
	int rightOne = eor & (~eor + 1);   // 提取出最右的1
	int onlyOne = 0;  //eor
	for(int i=0;i<arr.length;i++){
		if((arr[i] & rightOne) == 0){   //  我们这里让和最右侧的1异或结果不等于0,相当于我们和第八位为1的一类数做异或,不碰第八位为0的。
			onlyOne ^= arr[i];
		}
	}
	Systom.out.println(onlyOne + " " + (onlyOne^eor));
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Xray+awvs联动扫描

首先xray开启监听 xray_windows_amd64.exe webscan --listen 127.0.0.1:7777 --html-output xray-xxx.html --plugins sqldet,xxe,upload,brute-force,cmd-injection,struts,thinkphp 然后准备目标csv文件,每行一个url或ip然后加个逗号 接着awvs导入csv 对导进来的每个目…

沉痛悼念科研分公司

今天上班途中&#xff0c;遇到了上家公司的同事王强。他正准备去体检中心体检。几句寒暄之后&#xff0c;得知他是要入职选煤公司了。 我们所在的公司比较大&#xff0c;总公司下设有几十个分、子公司&#xff0c;我和他曾经在一家子公司——科研分公司。现在的科研分公司解散…

FIFO 位宽转换

从8位转32位 module tb_fifo();reg clk,rst; initial beginclk0;forever #4.545 clk~clk; end initial beginrst1;#9.09 rst0; endreg [31:0] cnts; always (posedge clk or posedge rst) beginif(rst)begincnts < 32d0;endelsebegincnts < cnts 1b1;end endreg […

中国电子云-隐私计算-云原生安全可信计算,物理-硬件-系统-云产品-云平台,数据安全防护

目录 联邦学习的架构思想 中国电子云-隐私计算-云原生安全 可信计算&#xff0c;物理-硬件-系统-云产品-云平台&#xff0c;数据安全防护 全栈国产信创的意义 1. 提升科技创新能力 2. 推动经济发展 3. 加强信息安全与自主可控 全栈国产信创的重要领域 1. 人工智能 2.…

硬件加速器及其深度神经网络模型的性能指标理解

前言&#xff1a; 现如今&#xff0c;深度神经网络模型和硬件加速器&#xff0c;如GPU、TPU等的关系可谓是“不分彼此”&#xff0c;随着模型参数的增加&#xff0c;硬件加速器成为了训练、推理深度神经网络不可或缺的一个工具&#xff0c;而近年来硬件加速器的发展也得益于加速…

AlphaFold更新了!AlphaFold-latest

AlphaFold又有重大更新了&#xff01;AlphaFold-latest来了&#xff01; &#x1f508;&#xff1a;号外号外&#xff01;Google DeepMind联合Isomorphic Labs在2023年10月31日发布了新一代的AlphaFold&#xff08;AlphaFold-latest&#xff09;。 AlphaFold-latest显着提高了…

论文阅读 - Detecting Social Bot on the Fly using Contrastive Learning

目录 摘要&#xff1a; 引言 3 问题定义 4 CBD 4.1 框架概述 4.2 Model Learning 4.2.1 通过 GCL 进行模型预训练 4.2.2 通过一致性损失进行模型微调 4.3 在线检测 5 实验 5.1 实验设置 5.2 性能比较 5.5 少量检测研究 6 结论 https://dl.acm.org/doi/pdf/10.1145/358…

Qt信号槽

目录 1、信号的定义 2、槽定义 3、信号和槽连接 4、信号与槽断开连接 5、伪代码展示 6、注意 Qt中的信号&#xff08;signals&#xff09;和槽&#xff08;slots&#xff09;是一种用于实现对象间通信的机制&#xff0c;广泛用于Qt应用程序中&#xff0c;特别是在图形用户…

【华为】路由器以PPPoE拨号接入广域网

组网需求 用户希望以PPPoE拨号方式接入广域网&#xff0c;如图1所示&#xff0c;Router作为PPPoE客户端&#xff0c;得到PPPoE服务器的认证后获得IP地址&#xff0c;实现用户接入互联网的需求。内网网关地址&#xff08;即VLANIF1接口的IP地址&#xff09;为10.137.32.1/24。 …

资源限流 + 本地分布式多重锁——高并发性能挡板,隔绝无效流量请求

前言 在高并发分布式下&#xff0c;我们往往采用分布式锁去维护一个同步互斥的业务需求&#xff0c;但是大家细想一下&#xff0c;在一些高TPS的业务场景下&#xff0c;让这些请求全部卡在获取分布式锁&#xff0c;这会造成什么问题&#xff1f; 瞬时高并发压垮系统 众所周知…

Go Metrics SDK Tag 校验性能优化实践

背景 Metrics SDK 是与字节内场时序数据库 ByteTSD 配套的用户指标打点 SDK&#xff0c;在字节内数十万服务中集成&#xff0c;应用广泛&#xff0c;因此 SDK 的性能优化是个重要和持续性的话题。本文主要以 Go Metrics SDK 为例&#xff0c;讲述对打点 API 的 hot-path 优化的…

当函数参数为一级指针,二级指针

当函数参数为一级指针&#xff0c;二级指针 在讲述内容之前&#xff0c;先讲四点重要知识 1.当传入参数时&#xff0c;函数形参会立即申请形参的内存空间&#xff0c;函数执行完毕后&#xff0c;形参的内存空间立即释放掉。 1.指针是存放其他变量地址的变量。指针有自己的内…

ECharts折线图去掉图例和线段上的小圆点

官方的初始效果 折线图的图例有小圆点&#xff0c;并且图表中也有小圆点 最终效果 去掉图例和图标中的小圆点 并且柱状图和折线图的图例要不同 代码实现 去掉图例小圆点 官方文档 itemStyle: { opacity: 0 } 折线图中的小圆点去掉 官方文档 两个代码二选一就行&#x…

设计模式04———桥接模式 c#

桥接模式&#xff1a;将一个事物从多个维度抽象出来&#xff0c;采用 分离 和 组合 的方式 替代 原本类的继承 桥接模式&#xff08;Bridge Pattern&#xff09;是一种软件设计模式&#xff0c;属于结构型模式&#xff0c;它用于将抽象部分与具体实现部分分离&#xff0c;以便它…

Jorani远程命令执行漏洞 CVE-2023-26469

Jorani远程命令执行漏洞 CVE-2023-26469 漏洞描述漏洞影响漏洞危害网络测绘Fofa: title"Jorani"Hunter: web.title"Jorani" 漏洞复现1. 获取cookie2. 构造poc3. 执行命令 漏洞描述 Jorani是一款开源的员工考勤和休假管理系统&#xff0c;适用于中小型企业…

EASYX实现多物体运动

eg1:单个物体运动使用easyx实现单个小球的运动 #include <stdio.h> #include <easyx.h> #include <iostream> #include <math.h> #include <stdlib.h> #include <conio.h> #include <time.h> #define PI 3.14 #define NODE_WIDTH 4…

API接口的定义|电商API接口的接入测试和参数说明【附代码实例教程】

一 . API接口的定义 API全称Application Programming Interface&#xff0c;即应用程序编程接口&#xff0c;是一些预先定义的函数&#xff0c;或指软件系统不同组成部分衔接的约定&#xff0c;用于传输数据和指令&#xff0c;使应用程序之间可以集成和共享数据资源。 简单来…

Android拖放startDragAndDrop拖拽onDrawShadow静态添加xml布局View,Kotlin(4)

Android拖放startDragAndDrop拖拽onDrawShadow静态添加xml布局View&#xff0c;Kotlin&#xff08;4&#xff09; import android.content.ClipData import android.graphics.Canvas import android.graphics.Point import android.os.Bundle import android.util.Log import a…

Jetson NX FFmpeg硬件编解码实现

最近在用Jetson Xavier NX板子做视频处理&#xff0c;但是CPU进行视频编解码&#xff0c;效率比较地下。 于是便考虑用硬解码来对视频进行处理。 通过jtop查看&#xff0c;发现板子是支持 NVENC硬件编解码的。 1、下载源码 因为需要对ffmpeg进行打补丁修改&#xff0c;因此需…

无需服务器内网穿透Windows下快速搭建个人WEB项目

&#x1f4d1;前言 本文主要是windows下内网穿透文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ 参考自&#xff1a;Windows搭建web站点&#xff1a;免费内网穿透发布至公网 &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是青衿&#x1f947; ☁️博客首…