# radix sort + quicksort principle

• As all elements occurs 3 times except only one, then we can think about that using bit sort of all elems, use >> operation of all elems and sort all elems, then surely, 0 group will have a(a%3==0) elements or 1 group have a(a%3==0) elements.
example:
2 (010),3(011),5(101),5(101),2(010),5(101),2(010)
firstly sort based on last bit, it will be:
2 (010),2(010), 2(010),5(101),5(101),5(101),3(011)

check that 0 group has 3 elems, and 1 group has 4 elems, so continue using sort on 2nd last bit from 3rd to 6nd elems.
5(101),5(101),5(101),3(011)
0 group has 3 elems, and 1 group has 1 elems. Continue using sort on 3rd last bit, and from 6nd to 6nd elems, since start== end, return 6nd elems.

``````public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0) return 0;

return getSingle(0, nums.length-1, nums, 0);
}

private int getSingle(int start, int end, int[] nums, int moveLeft) {
if (start == end) return nums[start];
int flag = (nums[start]>>moveLeft)&1;
int temp = nums[start];
int front = start, rear = end;
while (front < rear) {
while (front < rear && ((nums[rear]>>moveLeft)&1) != flag) rear--;
if (front < rear) nums[front] = nums[rear];
while (front < rear && ((nums[front]>>moveLeft)&1) == flag) front++;
if (front < rear) nums[rear] = nums[front];
}
nums[front] = temp;
if ((front-start+1)%3 != 0) return getSingle(start, front, nums, moveLeft+1);
else return getSingle(front+1, end, nums, moveLeft+1);
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.