問：給定一個數組 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)
1 回答
侃侃爾雅
TA貢獻1801條經驗 獲得超16個贊
這個問題的最佳情況是 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>() {
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();
}
添加回答
舉報
0/150
提交
取消