时间戳

首页 > 解决方案 > 优化程序以查找数组中的第 k 个最小元素（Java，预期时间复杂度 O(n)）

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

问题描述

问：给定一个数组 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)

标签： javaarrays

解决方案

这个问题的最佳情况是 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();

    }

推荐阅读