Java solution, both 2-pass and 1-pass


  • 34
    H
    public void sortColors(int[] nums) {
        // 1-pass
        int p1 = 0, p2 = nums.length - 1, index = 0;
        while (index <= p2) {
            if (nums[index] == 0) {
                nums[index] = nums[p1];
                nums[p1] = 0;
                p1++;
            }
            if (nums[index] == 2) {
                nums[index] = nums[p2];
                nums[p2] = 2;
                p2--;
                index--;
            }
            index++;
        }
    }
    

    public void sortColors(int[] nums) {
        // 2-pass
        int count0 = 0, count1 = 0, count2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {count0++;}
            if (nums[i] == 1) {count1++;}
            if (nums[i] == 2) {count2++;}
        }
        for(int i = 0; i < nums.length; i++) {
            if (i < count0) {nums[i] = 0;}
            else if (i < count0 + count1) {nums[i] = 1;}
            else {nums[i] = 2;}
        }
    }

  • 0
    R

    Javascript version:

    var sortColors = function(nums) {
        var p1 = 0, p2 =  nums.length -1, index = 0;
            while(index <= p2) {
                if(nums[index] == 0) {
                    nums[index] = nums[p1];
                    nums[p1] = 0;
                    p1++;
                }
                if(nums[index] == 2) {
                    nums[index] = nums[p2];
                    nums[p2] = 2;
                    p2--;
                    index--;
                }
                index++;
            }
    };
    

    Golang version:

    func sortColors(nums []int)  {
        p1 := 0
        p2 :=  len(nums) -1
        index := 0
        for(index <= p2) {
            if(nums[index] == 0) {
                nums[index] = nums[p1]
                nums[p1] = 0
                p1++
            }
            if(nums[index] == 2) {
                nums[index] = nums[p2]
                nums[p2] = 2
                p2--
                index--
            }
            index++
        }
    }
    

  • 0
    G

    concise Java version :--)

    	public static void sortColors(int []nums){
    		int red=0,white=0,blue=0;
    		for(int i=0;i!=nums.length;i++){//first, count their numbers
    			if(nums[i]==0){
    				red++;
    			}else if(nums[i]==1){
    				white++;
    			}else{
    				blue++;
    			}
    		}
    		for(int i=0;i!=nums.length;i++){//second, rewrite the original array
    			if(i<red){
    				nums[i]=0;
    			}else if(i<white+red){
    				nums[i]=1;
    			}else{
    				nums[i]=2;
    			}
    		}
    	}

Log in to reply
 

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