数组相同数字聚集

题目描述：

昨天做 leetcode 组合总和 II 这个题目时，碰到这样一个需求：给定一个数组，数组中存在相同的数字，不对数组排序，将相同的数字聚集在一起。要求时间复杂度为 O(n)，否则还不如直接排序呢，emm。

例如：{5, 3, 9, 3, 5, 3} 变为 {5, 5, 3, 3, 3, 9}。

问题求解

示例代码如下：

import java.util.HashMap;
public class Test {
    private static int[] gather(int[] A){
        int[] G = new int[A.length];
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for(int i = 0; i < A.length; ++i){ // 去重，计数
            int count = countMap.getOrDefault(A[i], 0);
            countMap.put(A[i], count+1);
        }
        int preCount = 0;
        for(int key : countMap.keySet()){ // 累加计数
            countMap.put(key, countMap.get(key)+preCount);
            preCount = countMap.get(key);
        }
        for(int i = 0; i < G.length; ++i){ // 聚集
            int k = countMap.get(A[i]);
            G[--k] = A[i];
            countMap.put(A[i], k);
        }
        return G;
    }
    public static void main(String[] args) {
        int[] A = {5,17,10,17,2,10,10,2,5,12,9,9,10};
        int[] G = gather(A);
        for(int i = 0; i < G.length; ++i){
            System.out.print(G[i] + "\t");
        }
    }
}

运行结果如下：

运行结果.png

从计数排序中获得灵感，算法步骤如下：

1. 计数，使用 HashMap 给原数组去重并计数。
2. 累加计数，累加后的计数表示对应元素在聚集数组中最后出现的位置。
3. 填数，每填一个数字，就将该数字对应的累加计数减一，表示下一个相同数字的所填位置。

例如对于输入 {5, 17, 10, 17, 2, 10, 10, 2, 5, 12, 9, 9, 10}
经过算法第一步处理后，HashMap 中的数据情况为 {17=2, 2=2, 5=2, 9=2, 10=4, 12=1}
经过算法第二步处理后，HashMap 中的数据情况为 {17=2, 2=4, 5=6, 9=8, 10=12, 12=13}。
经过算法第三步处理后，完成聚集，聚集数组为 {17, 17, 2, 2, 5, 5, 9, 9, 10, 10, 10, 10, 12}。举例说明一下填数的过程，例如 2，遍历原数组时碰到的第一个 2，填在聚集数组的第 4 个位置上（对应数组下标为 3），然后 4 减一变成 3，下一次再碰到 2 时，填在聚集数组的第 3 个位置上（对应数组下标为 2），以此类推，直到聚集完成。

由于使用的是 HashMap，遍历顺序与插入顺序无关，所以数字第一次出现的顺序会发生改变。如果想保持顺序不变，可以使用 LinkedHashMap 代替 HashMap。