radix sort + quicksort principle


  • 0
    X

    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);
    }

Log in to reply
 

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