使用时间复杂度为O(n + k*log(k))的算法对整数进行排序

Question

设计一种算法，对包含重复元素的n个整数进行排序，其中不同数字的总数为k。你的算法应该在O(n + k*log(k))的时间复杂度内运行。期望的运行时间足够快。对于哪些值的k，这个算法变成线性？

我无法想出一个符合条件必须是O(n + k*log(k))的整数排序算法。我不是一个很高级的程序员，但在这个问题前，我需要想出一个针对列表中所有数字xi的算法，其中0≤xi≤m，并且该算法的时间复杂度为O(n+m)，其中n是列表中的元素数量，m是列表中最大整数的值。我通过使用计数排序轻松解决了这个问题，但我在这个问题上遇到了困难。对我来说最困难的条件是ordo符号下的k*log(k)项，如果是n*log(n)代替，那么我就可以使用归并排序，对吧？但现在这不可能，所以任何想法都将非常有帮助。

提前感谢！

- Karl Karlsson

---

"设计一个算法..." - 你为什么认为命令我们做某事是可以的？请用礼貌的方式提出请求。 - Kelly Bundy

你可以使用O(k)的额外内存吗？ - Jim Mischel

提示：通过让问题看起来不像作业问题，可以增加获得更受欢迎/有趣答案的机会。之后再感谢我吧。 - adelriosantiago

Answer 1

以下是一种可能的解决方案：

• 使用哈希表，计算每个值的唯一值和重复值的数量。这应该具有O(n)的复杂度。

• 枚举哈希表，将唯一值存储到临时数组中。复杂度为O(k)。

• 使用标准算法（例如归并排序）对这个数组进行排序：复杂度为O(k.log(k))。

• 通过复制已排序的唯一值数组中的元素来创建结果数组，每个元素的次数存储在哈希表中。复杂度为O(n) + O(k)。

• 综合复杂度为O(n + k.log(k))。

例如，如果k是一个小常量，则对n个值的数组进行排序随着n越来越大而趋向于线性时间。

如果在第一阶段（其中逐步计算k）期间发现k与n没有显著差异，则放弃哈希表，只使用标准算法对原始数组进行排序。

- chqrlie

Answer 2

一个可能的Java解决方案可以是这样的：

public List<Integer> sortArrayWithDuplicates(List<Integer> arr) {

    // O(n)
    Set<Integer> set = new HashSet<>(arr);

    Map<Integer, Integer> freqMap = new HashMap<>();
    for(Integer i: arr) {
       freqMap.put(i, freqMap.getOrDefault(i, 0) + 1);
    }

    List<Integer> withoutDups = new ArrayList<>(set);

    // Sorting => O(k(log(k)))
    // as there are k different elements
    Arrays.sort(withoutDups);

    List<Integer> result = new ArrayList<>();

    for(Integer i : withoutDups) {
        int c = freqMap.get(i); 
        for(int j = 0; j < c; j++) {
            result.add(i);
        }
    }

    // return the result
    return result; 
}

以上代码的时间复杂度为 O(n + k*log(k))，解决方案与上面回答的一样。

- Pritam Banerjee

Answer 3

O(n + k*log(k)) 的运行时间（像运行时间中的加法一样）表明您有两个子程序，一个在 O(n) 中运行，另一个在 O(k*log(k)) 中运行。

1. 您可以首先在 O(n) 中计算元素的频率（例如在哈希映射中，如果您不熟悉它，请查阅相关资料，它非常有用）。

2. 然后，您只需对其中有 k 个的唯一元素进行排序。这个排序在 O(k*log(k)) 中运行，您可以使用任何排序算法。

最后，通过在步骤1中创建的映射中查找，将单个唯一元素替换为它们实际出现的次数。

- Moritz Groß