当前位置: 首页>后端>正文

[geeksforgeeks] sort a nearly sorted (or K sorted) array

题目

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(); 
        } 
    } 
}

https://www.xamrdz.com/backend/37g1925157.html

相关文章: