思路一:使用哈希的方式记录每一个数字出现的次数,最后将出现一次的数字存入到相应的数组之中去。
//num1,num2分别为长度为1的数组。传出参数 //将num1[0],num2[0]设置为返回结果 import java.util.*; public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { Map<Integer, Integer> map = new HashMap<>(); for(int val : array) { if(map.get(val) == null) { map.put(val, 1); } else { map.put(val, map.get(val) + 1); } } Set<Integer> set = map.keySet(); boolean flag = false; for(int val : set) { if(map.get(val) == 1) { if(!flag) { num1[0] = val; flag = true; } else { num2[0] = val; break; } } } } }
思路二:归并排序:https://blog.nowcoder.net/n/a17d9819e4fa4ae3ac9d1b41870a3296 ,在对数组进行排序后我们在遍历数组的时候就可以对重复的数字进行一个跳过,最终只保存出现一次的数字。
//num1,num2分别为长度为1的数组。传出参数 //将num1[0],num2[0]设置为返回结果 import java.util.*; public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { int[] temp = new int[array.length]; mergeSort(array, 0, array.length - 1, temp); int cnt = 0; for(int i = 0; i < array.length; ) { if(i == array.length - 1) { if(cnt != 0) num2[0] = array[i]; else num1[0] = array[i]; ++ cnt; ++ i; } else { if(array[i] == array[i + 1]) i += 2; //重复的数字必定重复出现 else { if(cnt != 0) num2[0] = array[i]; else num1[0] = array[i]; ++ cnt; ++ i; } } } } public void mergeSort(int[] array, int l, int r, int[] temp) { if(l >= r) return ; int mid = (l + r) >> 1; mergeSort(array, l, mid, temp); mergeSort(array, mid + 1, r, temp); Merge(array, l, mid, r, temp); } public void Merge(int[] array, int l, int mid, int r, int[] temp) { int i = l, j = mid + 1, cnt = l; while(i <= mid && j <= r) { if(array[i] <= array[j]) { temp[cnt ++] = array[i ++]; } else { temp[cnt ++] = array[j ++]; } } while(i <= mid) temp[cnt ++] = array[i ++]; while(j <= r) temp[cnt ++] = array[j ++]; for(int k = l; k <= r; ++ k) array[k] = temp[k]; } }
思路三:位运算,思维,首先我们将所有的数字进行异或和,我们知道 x ^ x = 0, 所以在进行所有数的异或和以后,我们就可以得到 num = num1 ^ num2,由于现在我们需要将这两个数字分离开来,这里直接给出思路:将 num 转换为二进制,从左到右我们可以找到第一个为 1 的位置,此时说明 num1 和 num2 的二进制在这个位置上面的数字分别为 1 和 0,接下来把所有数字转化为二进制,根据我们找到的第 i 位的二进制的不同可以将所有给出的数字分为两组,一组是第 i 位为 1 的数字,一组是第 i 位 为 0 的数字,最后分别对这两组数字进行一个异或和,那么最终得到的就是 num1 和 num2。
//num1,num2分别为长度为1的数组。传出参数 //将num1[0],num2[0]设置为返回结果 import java.util.*; public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { int val = 0, n = array.length; for(int temp : array) val ^= temp; int _val = 0, x = 0, y = 0; for(int i = 0; i < 31; ++ i) { if(((val >> i) & 1) == 1) { _val = (1 << i); } } for(int temp : array) { if((_val & temp) == _val) { x ^= temp; } else y ^= temp; } num1[0] = x; num2[0] = y; } }