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进制加法也可解决