Leetcode 215、数组中第k个最大的元素
2021-02-20 12:22
标签：复杂 tor 位置 top pivot find ble def 扫描 题目链接：kth-largest-element-in-an-array 方法1： 使用快速排序。 1、对数组进行partition，从left到right随机选择一个主元pivot，将pivot与left的元素交换位置。 另索引 j 初始为left，扫描从left + 1到right的元素，若小于pivot，则将其与 ++j 处的元素交换。 这样当扫描结束，left的元素即主元pivot，从left + 1到 j 的元素都大于pivot，从 j + 1到right的元素都小于等于pivot。 将left位置的元素与 j 位置的互换，则从left到 j-1 的元素都大于pivot，j 位置元素等于pivot，j 右边元素都小于等于pivot。 因此partition完成。返回pivot的位置 j。 2、若pivot的下标 idx 等于 k - 1，则pivot位置的元素即第K大的元素。 若idx大于 k - 1，另right = idx - 1，返回第一步在左边寻找。 若idx小于 k - 1，另left = idx + 1，返回第一步在右边寻找。 code: 方法2： 用优先队列实现。 1、可以用小顶堆，维护K个最大的元素。 先将数组前K个元素入堆，遍历数组的元素，当某元素大于堆顶元素，则堆顶出堆，将此元素加入。 最终堆顶元素即第K大的元素。 2、可用大顶堆，维护N - K + 1个最小的元素，这是因为第K大即第N - K + 1 小。 先将数组前N - K + 1个元素入堆，遍历数组的元素，当某元素小于堆顶元素，则堆顶出堆，将此元素加入。 最终堆顶元素即第K大的元素。 3、时间复杂度为O(NlogK)，空间复杂度为O(K)，因此当K
code: Leetcode 215、数组中第k个最大的元素 标签：复杂 tor 位置 top pivot find ble def 扫描 原文地址：https://www.cnblogs.com/lxc1910/p/12681716.html 1 class Solution:
2
3 def findKthLargest(self, nums: List[int], k: int) -> int:
4 def partition(nums, left, right):
5 pivot_idx = random.randint(left, right)
6 if nums[pivot_idx] != nums[left]:
7 nums[left], nums[pivot_idx] = nums[pivot_idx], nums[left]
8 pivot = nums[left]
9
10 j = left
11 for i in range(left + 1, right + 1):
12 if nums[i] > pivot:
13 j += 1
14 nums[j], nums[i] = nums[i], nums[j]
15 # nums[left] = pivot,nums[left+1...j] > pivot，交换后nums[left..j-1] > pivot,nums[j] = pivot,nums[j+1...right]
16 if nums[j] != nums[left]:
17 nums[j], nums[left] = nums[left], nums[j]
18 return j
19
20 left = 0
21 right = len(nums) - 1
22 while True:
23 idx = partition(nums, left, right)
24 if idx == k - 1:
25 return nums[idx]
26 elif idx > k - 1:
27 right = idx - 1
28 else:
29 left = idx + 1
1 class Solution {
2 public:
3 int findKlarge(vectorint>& nums, int k) {
4 priority_queueint, vectorint>, greaterint>> pq; //小顶堆
5 for (int i = 0; i ) {
6 pq.push(nums[i]);
7 }
8 for (int i = k; i ) {
9 if (nums[i] > pq.top()) {
10 pq.pop();
11 pq.push(nums[i]);
12 }
13 }
14 return pq.top();
15 }
16
17 int findKsmall(vectorint>& nums, int k) {
18 priority_queueint> pq; //默认大顶堆
19 for (int i = 0; i ) {
20 pq.push(nums[i]);
21 }
22 for (int i = k; i ) {
23 if (nums[i] pq.top()) {
24 pq.pop();
25 pq.push(nums[i]);
26 }
27 }
28 return pq.top();
29 }
30 int findKthLargest(vectorint>& nums, int k) {
31 if (k 2) {
32 return findKlarge(nums, k);
33 }
34 return findKsmall(nums, nums.size() - k + 1);
35 }
36 };
上一篇：unity3d之简单动画
下一篇：细谈Java中的时间与日期
文章标题：Leetcode 215、数组中第k个最大的元素
文章链接：http://soscw.com/index.php/essay/57983.html