Share my one pass and bucket sort solution


  • 0
    P

    //One pass solution
    public void sortColors(int[] nums) {

        int left=0;
        int right=nums.length-1;
    
        for(int i = 0;i<=right && left<=right;) {
            switch (nums[i]) {
                case 0:
                    swap(nums,i,left);
                    left++;
                    i=Math.max(left,i);
                    break;
                case 2:
                    swap(nums,i,right);
                    right--;
                    break;
                default:
                    i++;
                    break;
            }
        }
    }
    
    private void swap(int[] nums, int i,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    

    //bucket sort
    public void sortColors(int[] nums) {

        int[] count = new int[3];
        for(int i=0;i<nums.length;i++) {
            count[nums[i]]++;
        }
        int j=0;
        int t=0;
        while(j<3) {
            while(count[j]-->0) {
                nums[t++] = j;
            }
            j++;
        }
    }

Log in to reply
 

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