Java 8 : How to find kth smallest, 高效

Question

在java 8中如何有效地找到第K个最小的？第 K 个最小的是

http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

我已经在下面尝试过。如果有一个更有效的解决方案提供Java-8的安全性，例如在空数组等情况下我不应该在访问索引之前检查大小。我相信我自己的解决方案是安全的空数组。

如果存在我的 Java-8 方法和更好的 Java-8 方法的可证明的时间复杂度比较，我们将不胜感激。谢谢。

package lab.rat.jerry.kthsmallest;

import static java.util.stream.Collectors.toList;

import java.util.Arrays;
import java.util.List;

public class KthSmallest {

    // Inputs
    static int k = 3;

    static Integer[] myIntArray = {2, 3, 1, 4, -2, 0, -3, 0, -1, 5 };

    public static void main(String[] args) {

        List<Integer> list = Arrays.asList(myIntArray);

        System.out.println(list
            .stream()
            .sorted()
            .distinct()
            .limit(k)
            .skip(k-1)
            .collect(toList())
            );
    }
}

Answer 1

您可以在 Java 中使用简单的数据结构 PrioretyQueue。您可以快速获取和删除最大或最小元素:

public static int kthLargestElement(int[] nums, int k) {

    PriorityQueue<Integer> queue = new PriorityQueue<>();
    for (int i = 0; i < nums.length ; i++) {
        queue.add(nums[i]);
    }
    while (k > 1){
        queue.poll();
        k-=1;
    }
    return queue.poll();
}