假设您有一个大小为 n 的整数数组 A。您事先知道 A 的 O(√n) 个元素可以大于 2020(n)^(5) − 5n，并且A 的其余元素位于 [1, 2020n^5 − 5n] 范围内。事实证明，在这种情况下，在最坏的情况下，A 可以在 O(n) 时间内完成排序。
我正在尝试解决这个有趣的算法问题，我的直觉是使用基数排序作为我的解决方案的一部分。令我困惑的部分是 O(√n) 运行时，因此任何寻找此类算法的指针将不胜感激!
最佳答案
将范围内元素与范围外元素分开 (O(n))。对范围内的元素进行基数排序(基数为 n；对于 n ≥ 2020，这需要六遍，时间复杂度为 O(n))。对超出范围的元素进行插入排序(其中有 √n 个，因此 O(√n²) = O(n))。合并两个已排序的数组 (O(n))。
关于algorithm - 最坏情况为 O(n) 的基数排序算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/67405203/