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

Question

我有一个问题，试图实现一个算法使用分而治之。

给定一个未排序的数组tv[]查找该数组的de 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

分而治之

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

Answer 2

你为什么使用分而治之？

我建议你使用优先队列。你可以在谷歌上搜索更多关于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个最小的。