Quicksort like solution


  • 0
    E

    I am not able to come up with the bit manipulation solution. They are really brilliant. Here is a quicksort like solution, which should be easier to come up with. The best case should be O(n).

    public class Solution {
         Random rand = new Random();
    		
        public int singleNumber(int[] nums) {
            return helper(nums, 0, nums.length-1);
        }
        
        public int helper(int[] nums, int begin, int end){
            if(begin > end) return -1;//UNFOUND; not possible in this problem.
            if( begin == end) return nums[begin];
            int pivotIndex =  rand.nextInt(end-begin+1)+begin;
            swap(nums, pivotIndex, end);
            int pivot = nums[end];
            int p = begin;
            for(int i = begin; i < end; i++){
                if( nums[i] <= pivot){
                    swap(nums, i, p);
                    p++;
                }
            }
            swap(nums, p, end);
            
            if( (p - begin+1) % 3 != 0){
                return helper(nums, begin, p);
            }else{
                return helper(nums, p+1, end);
            }
            
        }
        
        public void swap(int[] nums, int i, int j){
            if(i == j) return;
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    

Log in to reply
 

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