题目
https://www.geeksforgeeks.org/nearly-sorted-algorithm/
给一个int array,有n个元素,每个元素离它正常sorted之后的位置的距离最多为K。请在O(nlogk)的时间内sort这个array。比如k=2,一个元素在sorted之后的array的index是7,现在还没sorted的时候,它能在的位置是5,6,7,8,9。
例子
Input : arr[] = {6, 5, 3, 2, 8, 10, 9}
k = 3
Output : arr[] = {2, 3, 5, 6, 8, 9, 10}
Input : arr[] = {10, 9, 8, 7, 4, 70, 60, 50}
k = 4
Output : arr[] = {4, 7, 8, 9, 10, 50, 60, 70}
解法
我们使用PriorityQueue。思路类似于滑动窗口。我们在PriorityQueue里面保持K+1
个元素,这些元素都是i
这个位置的candidates,我们通过PriorityQueue的滑动,来把candidates的最小值找到,排在i
这个位置上。
public class Solution {
public static void kSorted(int[] nums, int k) {
// min heap
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 把前 k + 1个元素加进去,因为排序后的第一个元素现在一定在这 k + 1个元素里
for (int i = 0; i <= k; i++) {
priorityQueue.offer(nums[i]);
}
int index = 0;
for (int i = k + 1; i < nums.length; i++) {
nums[index++] = priorityQueue.poll();
priorityQueue.offer(nums[i]);
}
while (priorityQueue.size() > 0) {
nums[index++] = priorityQueue.poll();
}
}
}