排颜色

问题描述

给定一个有n个对象（包括k种不同的颜色，并按照1到k进行编号）的数组，将对象进行分类使相同颜色的对象相邻，并按照1,2，...k的顺序进行排序。

1. 不能使用代码库中的排序函数来解决这个问题
2. k <= n

输出样例

输入: 
[3,2,2,1,4] 
4
输出: 
[1,2,2,3,4]
输入: 
[2,1,1,2,2] 
2
输出: 
[1,1,2,2,2]

挑战

一个相当直接的解决方案是使用计数排序扫描2遍的算法。这样你会花费O(k)的额外空间。你否能在不使用额外空间的情况下完成？

解题思路

直接排序 快速排序

计数排序

因为这道题目限定了要排序的数据范围 1-k k 小于数据的长度 所以可以利用空间换时间 把 时间复杂度缩小到 O（n）使用额外的存储空间来作为排序的中间状态。

public static void sortColors2(int[] colors, int k) {
        // write your code here
        int[] count = new int[k];
        for(int index=0; index < colors.length; index ++){
            count[colors[index] -1] ++;
        }
        int index = 0;
        int p = 0;
        while (index < colors.length){
            int t = 0;
            while (t < count[p]){
                colors[index] = p + 1;
                t ++;
                index ++;
            }
            p ++;
        }
    }

不使用这一块存储空间