找出数组中只出现一次的数字
2023-02-25 18:17:39 时间
一个数组中,有一个数字只出现一次,其余的数都出现两次,求出那个单独的数
可以使用异或或来解决这个问题,因为两个相同的数异或之后就是0,0与一个数异或还是这个数,而且异或满足交换律
public static void main(String[] args) {
int[] arr = {1, 2, 3, 2, 1};
int n=0;
for (int i = 0; i < arr.length; i++) {
n ^= arr[i];//与sun+=arr[i]类似,方便理解
}
System.out.println(n);
}
拓展:
一个数组中,只有两个不同的数字出现一次,其余的数都出现两次,求出那两个只出现一次的数
思路:假设数组是{1,2,3,1},要想找到那两个只出现一次的数,只需要将数组里面所有的数字异或一下,得到结果sum,然后将sum进行移位操作判断是否为1,如果不为1,依次往后,知道右移到位为1的时候为止,其实就是确定sum从右往左数第几位是1,从而起到筛选的作用,
接下来将数组遍历一遍,判断数组中的每个数是否满足移k位结果是否为1,(((sum >> k) & 1)是常见的判断位数上是1还是0的方法),如果是1,就将其全部异或起来,这样就可以找到num1
当找到num1时,num2=sum^num1,因为sum=num1 ^num2,所以在异或一个num1就可以得到num2
总结:简单来说,就是通过移位操作来达到分类的作用,接下来就是使用之前异或的方法即可
代码如下
public static int[] Search(int[] arr) {
int sum = 0;
int num1 = 0;
int num2 = 0;
int k = 0;
for (int i = 0; i < arr.length; i++) {
sum ^= arr[i];
}
while (((sum >> k) & 1) != 1) {
k++;
}
for (int i = 0; i < arr.length; i++) {
if ((arr[i] >> k & 1) == 1) {
num1 ^= arr[i];
}
}
num2 = sum ^ num1;
return new int[]{num1, num2};
}
public static void main(String[] args) {
int[] arr = {6, 3, 2, 4, 3, 6};
System.out.println(Arrays.toString(Search(arr)));
}
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023