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

Question

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

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

进行排序

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

因为我无法编辑传递的数组，所以我想不出另一种方法来对数组进行排序，而不是将它保存在另一个局部变量上，或者尝试像快速排序那样划分数组并返回 [ 的最后一个元素所在的位置=21=]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。您可以 google 更多关于 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小的。

Answer 2

分而治之

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

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

Divide and conquer - k element of unsorted array

java

arrays

sorting

algorithm

divide-and-conquer