class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
}
};
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104原站题解
python3 解法, 执行用时: 228 ms, 内存消耗: 24.6 MB, 提交时间: 2022-08-02 15:11:33
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
# 从大到小排第k个元素
n = len(nums)
def quick_select(nums, l, r):
while l <= r:
i = random.randint(l, r)
nums[r], nums[i] = nums[i], nums[r]
povit = r
i, j = l, l
while j < r:
if nums[j] > nums[povit]:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j += 1
nums[i], nums[povit] = nums[povit], nums[i]
if i == k - 1:
return nums[i]
elif i < k - 1:
l = i + 1
else:
r = i - 1
return quick_select(nums, 0, n-1)
python3 解法, 执行用时: 156 ms, 内存消耗: 24.7 MB, 提交时间: 2022-08-02 15:10:59
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
import heapq
heap = []
for i in nums:
heapq.heappush(heap,-i)
res = 0
for i in range(k):
res = -heapq.heappop(heap)
return res
python3 解法, 执行用时: 148 ms, 内存消耗: 24.7 MB, 提交时间: 2022-08-02 15:10:39
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
import heapq
heap = []
for i in range(k):
heapq.heappush(heap, nums[i])
n = len(nums)
for i in range(k, n):
if nums[i] > heap[0]:
heapq.heappush(heap, nums[i])
if len(heap) > k:
heapq.heappop(heap)
return heap[0]
python3 解法, 执行用时: 56 ms, 内存消耗: N/A, 提交时间: 2018-09-26 21:35:58
class Solution:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
nums.sort()
return nums[-k]