优化程序以找到数组中的第 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 个元素进行排序。

1. O(n) 遍历数组

2. O(logk) 用于使用堆排序对 k 个元素进行排序。

public Integer getKthEle(Integer[] numbers, int k) {

PriorityQueue<Integer> maxHeap = new PriorityQueue(k, new Comparator<Integer>() {

    public int compare(Integer a, Integer b) {

        return b-a;

    }

    }

);

for(int i=0;i<k;i++) {

    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 queue

for(int i=k;i<numbers.length;i++) {

    if(numbers[i] < maxHeap.peek()) {

        maxHeap.offer(numbers[i]);

        maxHeap.poll();

    } 

}

return maxHeap.peek();

}