对几乎排序的数组排序（元素错位不超过k）
最近有人问我这个面试问题：
您将得到一个几乎已排序的数组，因为每个N元素的错位可能不超过k正确排序顺序的位置。寻找一种时空高效的算法对数组进行排序。
我有以下O(N log k)解决方案。
让我们来表示arr[0..n)从索引0（包括）到N（不包括）的数组元素。
分类 arr[0..2k) 现在我们知道arr[0..k)它们处于最终的排序位置... ...但是arr[k..2k)可能仍然被放错位置k！ 分类 arr[k..3k) 现在我们知道arr[k..2k)它们处于最终的排序位置... ...但arr[2k..3k)可能仍会被k 分类 arr[2k..4k) .... arr[ik..N)在完成排序之前，就完成了！ 当您2k剩余的元素少于时，此最后一步可能会比其他步骤便宜 在每个步骤中，您最多要对中的2k元素进行排序，请O(k log k)至少k在每个步骤的末尾将元素置于其最终排序位置。有O(N/k)步骤，因此总体复杂度为O(N log k)。
我的问题是：
是O(N log k)最优的吗？这可以改善吗？ 您能做到这一点而无需（部分）重新排序相同的元素吗？ 问题来源于stack overflow
写回答
-
已经指出，一种渐近最优的解决方案使用最小堆，我只想提供Java代码：
public void sortNearlySorted(int[] nums, int k) { PriorityQueue minHeap = new PriorityQueue<>(); for (int i = 0; i < k; i++) { minHeap.add(nums[i]); }
for (int i = 0; i < nums.length; i++) { if (i + k < nums.length) { minHeap.add(nums[i + k]); } nums[i] = minHeap.remove(); } }
2020-02-09 13:05:43赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
