資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究尋找線性時間中第 k 個最小元素的 Python 程式
假設我們有一個名為 nums 的數字列表，我們還有另一個值 k，我們必須在列表中找到第 k 個（從 0 開始）的最小元素。我們必須在平均時間複雜度為 O(n) 的情況下解決這個問題。
因此，如果輸入為 nums = [6, 4, 9, 3, 1] k = 2，則輸出將為 4，因為排序後的列表將變為 [1, 3, 4, 6, 9]，第 k 個最小元素為 4。
為了解決這個問題，我們將按照以下步驟進行 -
- maxHeap := 一個新建立的空堆
- 對 0 到 k 範圍內的 i 迴圈操作
- 將 nums[i] 插入到 maxHeap 中
- 對 k + 1 到 nums 長度 - 1 範圍內的 i 迴圈操作
- 如果 nums[i] > maxHeap[0]，則
- 在 maxHeap 中刪除頂部
- 將 nums[i] 插入到 maxHeap 中
- 如果 nums[i] > maxHeap[0]，則
- 返回 maxHeap[0]
示例
讓我們看看以下實現來加深理解 -
from heapq import heappop, heappush def solve(nums, k): maxHeap = [] for i in range(k + 1): heappush(maxHeap, -nums[i]) for i in range(k + 1, len(nums)): if nums[i] < -maxHeap[0]: heappop(maxHeap) heappush(maxHeap, -nums[i]) return -maxHeap[0] nums = [6, 4, 9, 3, 1] k = 2 print(solve(nums, k))
輸入
[6, 4, 9, 3, 1], 2
輸出
4
更新於：19-10-2021
2K+ 瀏覽量
廣告