优化程序以找到数组中的第 k 个最小元素（Java，预期时间复杂度 O(n)）

Question

问：给定一个数组 arr[] 和一个数字 K，其中 K 小于数组的大小，任务是在给定数组中找到第 K 个最小的元素。假设所有数组元素都是不同的。

我已经浏览了与这个问题相关的所有帖子，但没有一个能帮助我解决时间复杂度问题。我是编码新手，很难优化我的解决方案。

预期时间复杂度为 O(n)

这是我的函数，时间复杂度为 O(nlogn)：

public static void smallestk(int arr[],int k)

{

    Arrays.sort(arr);

    System.out.println(arr[k-1]);

}

输出是正确的，但我想将我的代码从 O(nlogn) 优化到 O(n)

Answer 1

这个问题的最佳情况是 O(nlogk)，我们可以使用最大或最小堆数据结构来解决这个问题。如果 k 很小，这将接近 O(n)。这个想法是我们不必对整个数组进行排序，而是取一个大小为 k 的堆，并始终对堆中存在的 k 个元素进行排序。O(n) 遍历数组O(logk) 用于使用堆排序对 k 个元素进行排序。public Integer getKthEle(Integer[] numbers, int k) {PriorityQueue<Integer> maxHeap = new PriorityQueue(k, new Comparator<Integer>() {&nbsp; &nbsp; public int compare(Integer a, Integer b) {&nbsp; &nbsp; &nbsp; &nbsp; return b-a;&nbsp; &nbsp; }&nbsp; &nbsp; });for(int i=0;i<k;i++) {&nbsp; &nbsp; maxHeap.offer(numbers[i]);}// maintain the size k by adding to the queue if the next element is smaller than the head of the queue; remove from the head of the queue which is the largest element in the queuefor(int i=k;i<numbers.length;i++) {&nbsp; &nbsp; if(numbers[i] < maxHeap.peek()) {&nbsp; &nbsp; &nbsp; &nbsp; maxHeap.offer(numbers[i]);&nbsp; &nbsp; &nbsp; &nbsp; maxHeap.poll();&nbsp; &nbsp; }&nbsp;}return maxHeap.peek();}