找出数组中只出现一次的数字
数组 数字 出现 一次 找出
2023-06-13 09:16:42 时间
一个数组中,有一个数字只出现一次,其余的数都出现两次,求出那个单独的数
可以使用异或或来解决这个问题,因为两个相同的数异或之后就是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)));
}
相关文章
- 数组中第 K 大的数
- String转成Json数组 JsonArray 保持有序
- php拼接循环拼接字符串数组,PHP数组拼接
- C语言 数组倒序输出数字「建议收藏」
- 剑指 Offer 56 – I. 数组中数字出现的次数
- 189. 旋转数组
- 剑指37-数字在排序数组中出现的次数
- 剑指50-数组中重复的数字
- 剑指offer|03. 数组中重复的数字
- 【剑指offer|1.数组中重复的数字】
- 【剑指offer|5.在排序数组中查找数字I】
- PHP 如何从关联数组移除指定的键值对
- Java学习笔记之五java数组详解编程语言
- 学习Linux C编程之字符数组实战(linuxc字符数组)
- ASP获取网页全部图片地址并保存为数组的正则
- javascriptArray.remove()数组删除
- javascript定义初始化数组函数
- javascript数组操作实用技巧
- 《PHP编程最快明白》第二讲数字、浮点、布尔型、字符串和数组
- js中将具有数字属性名的对象转换为数组
- C++结构体数组详细解析
- 5种PHP创建数组的实例代码分享
- perl命令行参数内建数组@ARGV浅析
- JavaScript实现找出数组中最长的连续数字序列