題目
https://www.geeksforgeeks.org/nearly-sorted-algorithm/
給一個(gè)int array生巡，有n個(gè)元素璃俗，每個(gè)元素離它正常sorted之后的位置的距離最多為K。請(qǐng)?jiān)贠(nlogk)的時(shí)間內(nèi)sort這個(gè)array。比如k=2，一個(gè)元素在sorted之后的array的index是7鹅龄，現(xiàn)在還沒sorted的時(shí)候，它能在的位置是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蜗搔。思路類似于滑動(dòng)窗口。我們?cè)赑riorityQueue里面保持K+1個(gè)元素侨糟，這些元素都是i這個(gè)位置的candidates碍扔，我們通過PriorityQueue的滑動(dòng)瘩燥，來把candidates的最小值找到秕重，排在i這個(gè)位置上。
public class Solution {
public static void kSorted(int[] nums, int k) {
// min heap
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 把前 k + 1個(gè)元素加進(jìn)去厉膀，因?yàn)榕判蚝蟮牡谝粋€(gè)元素現(xiàn)在一定在這 k + 1個(gè)元素里
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();
}
}
}
