Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.
Have you met this question in a real interview?
Yes
Example
Given colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].
Note
You are not suppose to use the library's sort function for this problem.
Challenge
A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory. Can you do it without using extra memory?
Tags Expand
Related Problems Expand
class Solution { /** * @param colors: A list of integer * @param k: An integer * @return: nothing */ public void sortColors2(int[] colors, int k) { // write your code here int[] count = new int[k]; for(Integer color:colors){ count[color-1]++; } int index = 0; for(int i = 0 ; i < k ; i++){ while(count[i]>0){ colors[index++] = i+1; count[i]--; } } } }