数组中只出现一次的数字

题目描述解法一解法二

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

解法一

时间复杂度O(n),空间O(n) 使用一个Map来存储每个数值以及其对应的计数，最后遍历输出这个计数为1的两个值 //num1,num2分别为长度为1的数组。传出参数 //将num1[0],num2[0]设置为返回结果 import java.util.Map; import java.util.HashMap; public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { Map<Integer, Integer> map = new HashMap<>(); for(int n : array){ if(map.containsKey(n)){ map.put(n, 2); }else{ map.put(n, 1); } } int i = 0; for(Integer key : map.keySet()){ if(map.get(key) == 1){ if(i == 0){ num1[0] = key; i++; } else{ num2[0] = key; break; } } } } }

解法二

时间O(n)，空间O(1) //num1,num2分别为长度为1的数组。传出参数 //将num1[0],num2[0]设置为返回结果 //根据异或运算的性质 //n^0 = n //n^n = 0 //n*n*m = m; //若将数组中的连续异或（即res=x[0]^..^x[n]），异或后的结果res即是两个不同的数异或后的结果 //由于两个数值不想同，那么异或结果res对应的二进制中必定至少存在1位为1。 //使用res=res^(-res)可以得到res二进制中第一个1出现的地方。 //再将原数组中的元素分为两组，该位为1的数为一组，其余为另一组。（那么值相等的一定会被分到同一组） //再将两组中的值分别做连续异或，相同的值会互相抵消，最后的结果就是num1和num2的值 public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { int res = 0;//异或的结果 for(int num : array){ res ^= num; } num1[0] = 0; num2[0] = 0; res = res & (-res);//找出异或结果中出现1的位置 for(int num : array){ if((res & num) >= 1){//分组，该位为1，and运算的结果必定大于1 num1[0] ^= num; } else{ num2[0] ^= num; } } } }