java - 分而治之 - 未排序数组的 k 元素

Question

我在尝试使用分而治之算法时遇到问题。

给定一个未排序的数组 T v[] 找到该数组的 v[k] 元素，就好像该数组已排序但未对数组 v 排序.

例如，如果 k = 3 且 v = {2, -1, -6, 7, 4} 该数组的第 k 个元素是 2。

因为我无法编辑传递的数组，所以我想不出另一种方法来对数组进行排序而不将其保存在另一个局部变量上或尝试像快速排序那样划分数组并返回 最后一个元素所在的位置v 应该是。

如果有帮助，这是我的代码:

public static <T extends Comparable<? super T>> T kesimoRec(T v[], int izq, int der, int k) {
    if(izq < der){
    int inf = izq-1;
    T pivote = v[der];
       for(int i = izq; i < der; ++i){
           if(pivote.compareTo(v[i]) >= 0){
               ++inf;
           }
       }
       ++inf;
       if(inf > izq + k-1){
           return (kesimoRec(v, izq, inf-1, k));
       }else if( inf < izq + k-1){
           return (kesimoRec(v, inf+1, der, k-inf+izq-1));
       }else{
           return v[inf];
       }
    }else{
        return v[der];
    }
}

Answer 1

为什么要使用分而治之？

我建议您使用 PriorityQueue。你可以谷歌更多关于 PriorityQueue。了解其工作原理后，您会发现很容易想出解决方案。我的java代码:

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(nums.length);

        for (int num : nums) {
            queue.offer(num);
        }

        for (int i = 0; i < nums.length - k; i++) {
            queue.poll();
        }

        return queue.peek();
    }
}

嗯，抱歉，我的解决方案是找到第 k 个最大的，但你可以修改它以找到第 k 个最小的。