No elegant but plain and simple O(n) solution


  • 0
    H
    public void sortColors(int[] nums) {
        int zero = 0, one = 0, two = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0)
                zero ++;
            else if (nums[i] == 1)
                one ++;
            else // nums[i] == 2
                two ++;
        }
    
        for (int i = 0; i < zero; i++) 
            nums[i] = 0;
        for (int i = zero; i < zero+one; i++) 
            nums[i] = 1;
        for (int i = zero+one; i < zero+one+two; i++) 
            nums[i] = 2;
            
    
    }

  • 0
    S

    Same here. Just make it more straightforward.

    void sortColors(int* nums, int numsSize) {
        int colorCount[3] = {0};
        int i, j, idx = 0;
    
        for (i = 0; i < numsSize; i++)
            colorCount[nums[i]]++;
    
        for (i = 0; i < 3; i++)
            for(j = 0; j < colorCount[i]; j++)
                nums[idx++] = i;
    }

  • 0
    J

    Thank you!! very easy solution!!!!!!


Log in to reply
 

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