题目：
一个整型数组里除了两个数字（互不相同）之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
输入
第一行：数组的长度N(1<n<100000)
第二行：N个整数，空格隔开
输出
只出现了1次的那两个数，小的在前大的在后，空格隔开
样例输入
10
5 5 6 7 9 9 7 3 3 2
样例输出
2 6
思路：
1.已知把一个数组内元素遍历异或运算后，会消去里面相同的数（之前解释过），显然
当数组里有两个单独的数时，遍历异或肯定得不到两个解，但会得到一个不为零的解。
2.易知该解的二进制一定至少有一位为1，即可用这一位来控制将原数组分开做异或运算，
最终将得到这两个孤立的数。
3.与一个数二进制第一个1做比较操作，可以简单设置一个flag 整型标记，初值为1，通过
while循环 不断进行 flag >>= 1，操作找到该位置。在通过flag将数组分开运算。
（Java语言描述）
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
int min = 0;
int max = 0;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < arr.length; i++) {
int num = sc.nextInt();
arr[i] = num;
}
int temp = 0;//遍历异或 后那个标尺数
for(int i = 0; i < arr.length; i++) {
temp = temp^arr[i];
}
int flag = 1;//第一个不同的1
while((flag&temp) == 0) {
flag = flag << 1;
}
for(int i = 0; i < arr.length; i++) {
if((flag & arr[i]) == 0) {//表示在该位置上二者不同
min = min^arr[i];
}else {
max = max^arr[i];
}
}
int temp1 = 0;
if(max < min) {
temp1 = max;
max = min;
min = temp1;
}
System.out.println(min+" "+max);
}
}
网友评论