Given an array of n elements, where each element is at most k away from its target position, you need to sort the array optimally.
Example 1:
Input:
n = 7, k = 3
arr[] = {6,5,3,2,8,10,9}
Output: 2 3 5 6 8 9 10
Explanation: The sorted array will be
2 3 5 6 8 9 10
Example 2:
Input:
n = 5, k = 2
arr[] = {3,1,4,2,5}
Output: 1 2 3 4 5
Note: DO NOT use STL sort() function for this question.
Your Task:
You are required to complete the method nearlySorted() which takes 3 arguments and returns the sorted array.
Expected Time Complexity : O(nlogk)
Expected Auxilliary Space : O(n)
Constraints:
1 ≤ n ≤ 106
1 ≤ k < n
1 ≤ arri ≤ 107
class Solution { ArrayList <Integer> nearlySorted(int arr[], int num, int k) { //使用一个小顶堆来保持一个k size的window，每次取出最小元素 PriorityQueue<Integer> pq = new PriorityQueue<>(); int curr = 0; for(int i = 0; i < arr.length; i++) { pq.offer(arr[i]); //如果so far已经超过k个元素，那么可以开始输出元素 if(i >= k) { arr[curr++] = pq.poll(); } } while(!pq.isEmpty()) { arr[curr++] = pq.poll(); } ArrayList<Integer> list = new ArrayList(); for(int n : arr) list.add(n); return list; } }