counting sort, and Move-zeroes like solution


  • 0
    M

    counting sort:

      public void sortColors(int[] nums) {
        //count number of three colors
        int numOfRed = 0;
        int numOfBlue = 0;
        int numOfWhite = 0;
        if (nums.length == 0 || nums == null) return;
    
        //count red
        for (int i : nums) {
          if (i == 0) numOfRed++;
        }
        for (int i : nums) {//count white
          if (i == 1) numOfWhite++;
        }
        numOfBlue = nums.length - numOfRed - numOfWhite;
        for (int i = 0; i < numOfRed; i++) {
          nums[i] = 0;
        }
        for (int i = numOfRed; i < numOfRed + numOfWhite; i++) {
          nums[i] = 1;
        }
        for (int i = numOfRed + numOfWhite; i < nums.length; i++) {
          nums[i] = 2;
        }
      }
    

    Move-zeroes like solution

      public void sortColors(int[] nums) {
        if (nums.length == 0 || nums == null) return;
        //pholosophy of this question is very like move zeroes
        int redIndex = 0;
        int numOfWhite = 0;
    
        for (int i = 0; i < nums.length; i++) {
          if (nums[i] == 0) {
            nums[redIndex++] = 0;
          }
          else if (nums[i] == 1) {
            numOfWhite++;
          }
        }
    
        for (int i = redIndex; i <= redIndex + numOfWhite; i++) {
          nums[i] = 1;
        }
        for (int i = redIndex + numOfWhite; i < nums.length; i++) {
          nums[i] = 2;
        }
      }
    

Log in to reply
 

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