Using BucketSort


  • 0
    A
    public class Solution {
        public void sortColors(int[] nums) {
            //no need to sort
            if(nums.length <=1) return;
            int numColors = 3;
            
            //we can use bucket sort
            int[] buckets = new int[numColors];
            
            for(int i=0;i<nums.length;i++){
                buckets[nums[i]]++;
            }
            
            int j = 0;
            for(int i = 0;i < numColors;i++){
                int n = buckets[i];
                if(n > 0){
                   while(j< nums.length && n > 0){
                     nums[j++] = i;
                     n--;
                   } 
                }
            }
            
        }
    }
    

Log in to reply
 

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