最容易想到的办法 brutal force traversal
1.排序 2.查找
public int singleNumber(int[] nums) {
mergeSort(nums);
for(int element:nums){
System.out.println(element+",");
}
for(int i=0;i<nums.length;i+=2){
if((i+1)==nums.length){
return nums[i];
}
if(nums[i]!=nums[i+1]){
return nums[i];
}
}
return 0;
}
//归并排序
public static void mergeSort(int[] arr){
_mergeSort(arr, 0, arr.length);
}
public static void _mergeSort(int[] arr, int left, int right){
if(right - left <= 1){
return;
}
int mid = (left + right) / 2;
_mergeSort(arr, left, mid);
_mergeSort(arr, mid, right);
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right){
int[] tmp = new int[right - left];
int tmpSize = 0;
int l = left;
int r = mid;
while (l < mid && r < right){
//归并排序是稳定排序！！！
//此处的条件不要写作 arr[l] < arr[r]
if(arr[l] <= arr[r]){
//arr[l]比较小，就把这个元素先插入到 tmp 数组末尾
tmp[tmpSize] = arr[l];
tmpSize++;
l++;
}else{
//arr[r] 比较小，就把这个数组插入到 tmp 数组末尾
tmp[tmpSize] = arr[r];
tmpSize++;
r++;
}
}
//当其中一个数组遍历完了之后，就把另外一个数组的剩余部分都拷贝到 临时空间tmp
while (l < mid){
//剩下的都是左半边数组
tmp[tmpSize] = arr[l];
tmpSize++;
l++;
}
while (r < right){
//剩下的是右半边数组
tmp[tmpSize] = arr[r];
tmpSize++;
r++;
}
//最后一步，再把临时空间的内容都拷贝回参数数组
//需要把 tmp 中的内容拷贝回 arr 的 [left, right) 这一段空间里
// [left, right) 这个空间很可能不是从 0 开始的
for(int i = 0; i < tmp.length; i++){
arr[left + i] = tmp[i];
}
}
方法二：
充分利用Set数据结构里的数据唯一性，对重复的数组进行去重：
2*(不重复数组的和)?-(原数组的合)=重复的数字，这个解决问题的思路之前遇到过，这次没有灵活变通，所以要举一反三真的不容易。
public int singleNumber(int[] nums) {
HashSet<Integer> singleSet=new HashSet<Integer>();
int twiceSums=0;
int singleSums=0;
for(int element:nums){
singleSet.add(element);
twiceSums+=element;
}
for(int element:singleSet){
singleSums+=element;
}
return singleSums*2-twiceSums;
}方法三：最巧妙的位运算
public int singleNumberExclusiveOR(int[] nums){
// 使用位运算。对于这道题，可使用异或运算s⊕。异或运算有以下三个性质。
// 任何数和 0做异或运算，结果仍然是原来的数，即a⊕0=a。
// 任何数和其自身做异或运算，结果是 0，即 a⊕a=0 a⊕a=0。
// 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b
int result=0;
for(int elements:nums){
result^=elements;
}
return result;
}
