找到一个时间复杂度为 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) 而不是我可以使用合并排序，对吗？但现在这是不可能的，所以任何想法都会很有帮助。

提前致谢！

Answer 1

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

使用散列table，计算每个值的唯一值的数量和重复的数量。这应该具有 O(n).
枚举散列table，将唯一值存储到临时数组中。复杂度为 O(k).
使用标准算法（例如归并排序）对该数组进行排序：复杂度为 O(k.log(k)).
通过复制已排序的唯一值数组的元素来创建结果数组，每次复制存储在散列中的次数 table。复杂度是 O(n) + O(k).
组合复杂度为 O(n + k.log(k)).

例如，如果 k 是一个小常数，则对 n 值的数组排序会收敛于线性时间，因为 n越来越大

如果在第一阶段，k 是增量计算的，看起来 k 并不明显小于 n，删除散列 table 并使用标准算法对原始数组进行排序。

Answer 2

O(n + k*log(k) 的运行时表示（就像运行时中的加法一样）您有 2 个子例程，一个在 O(n) 中运行，另一个在 O(k*log(k)) 中运行。

您可以先计算 O(n) 中元素的频率（例如在Hashmap，不熟悉的可以看看这个，很有用。
然后你只需对 unique 个元素进行排序，从中有 k。此排序在 O(k*log(k)) 中运行，使用您想要的任何排序算法。

最后，通过在您在步骤 1 中创建的地图中查找，将单个唯一元素替换为它们实际出现的频率。

Answer 3

可能的 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))，解决方案与上面的回答在同一行。

找到一个时间复杂度为 O(n + k*log(k)) 的整数排序算法

Find an algorithm for sorting integers with time complexity O(n + k*log(k))

algorithm

sorting

time-complexity

mergesort

counting-sort