Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
题目解析：数组都是3个3个出现。找出唯一的数字。这个是在2个2个出现的升级版，2个2个直接异或就可以
解题思路：先用快排将数组排序，然后维护一个times和result字段，另其初始为2。假设下一个数跟前一个数相等，则times--，当times为01说明3个已经过去，将times又一次赋值为3，result=nums[i]。依照这样的方式遍历一边就可以，这里的这个小技巧来自剑指offer面试题29。以下上AC代码
public int singleNumber(int[] array) {
// 安全性检查 数组是否符合3*n+1;
float len = array.length;
if(len==1.0)
return array[0];
if ((len - 1) % 3 != 0 || len < 4)
return -1;
quick_sort(array, 0, array.length - 1);
int FindNum = array[0];
int times = 2;
for (int i = 1; i < len; i++) {
if (times == 0) {
// 换下一个数，times置为3又一次開始
FindNum = array[i];
times = 3;
}
if (FindNum == array[i])
times--;
}
return FindNum;
}
// 高速排序
private static void quick_sort(int[] arr, int low, int high) {
// 解决和合并
if (low <= high) {
int mid = partition(arr, low, high);
// 递归
quick_sort(arr, low, mid - 1);
quick_sort(arr, mid + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
// 分解
int pivot = arr[high];
int i = low - 1;
int temp;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换中间元素和privot
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}思路二：因为2个2个使用异或，即不进位的2进制加法。这里我们能够定义一个不进位的3进制加法也可解决