关键词：
题目链接：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:
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] <= pivot 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
方法2：
用优先队列实现。
1、可以用小顶堆，维护K个最大的元素。
先将数组前K个元素入堆，遍历数组的元素，当某元素大于堆顶元素，则堆顶出堆，将此元素加入。
最终堆顶元素即第K大的元素。
2、可用大顶堆，维护N - K + 1个最小的元素，这是因为第K大即第N - K + 1 小。
先将数组前N - K + 1个元素入堆，遍历数组的元素，当某元素小于堆顶元素，则堆顶出堆，将此元素加入。
最终堆顶元素即第K大的元素。
3、时间复杂度为O(NlogK)，空间复杂度为O(K)，因此当K < N / 2，用小顶堆，否则大顶堆。
code:
1 class Solution 2 public: 3 int findKlarge(vector<int>& nums, int k) 4 priority_queue<int, vector<int>, greater<int>> pq; //小顶堆 5 for (int i = 0; i < k; i++) 6 pq.push(nums[i]); 7 8 for (int i = k; i < nums.size(); 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(vector<int>& nums, int k) 18 priority_queue<int> pq; //默认大顶堆 19 for (int i = 0; i < k; i++) 20 pq.push(nums[i]); 21 22 for (int i = k; i < nums.size(); 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(vector<int>& nums, int k) 31 if (k < nums.size() / 2) 32 return findKlarge(nums, k); 33 34 return findKsmall(nums, nums.size() - k + 1); 35 36 ;
leetcode215.数组中的第k个最大元素(代码片段)
给定整数数组nums和整数k，请返回数组中第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。示例： 输入：[3,2,1,5,6,4]和k=2 输出：5思路：寻找数组... 查看详情
leetcode：数组中的第k个最大元素215(代码片段)
LeetCode：数组中的第K个最大元素【215】题目描述在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。示例1:输入:[3,2,1,5,6,4]和k=2输出:5示例 2:输入:... 查看详情
⭐算法入门⭐《哈希表》中等05——leetcode215.数组中的第k个最大元素(代码片段)
文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述 给定整数数组nums和整数k，请返回数组中第k个最大的元素。请... 查看详情
[leetcode]215.数组中的第k个最大元素(代码片段)
215.数组中的第K个最大元素Difficulty:中等在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。示例1:输入:[3,2,1,5,6,4]和k=2输出:5示例?2:输入:[3,2,3,1,2,4,5,5,6]和k=4输... 查看详情
leetcode215.数组中的第k个最大元素|python(代码片段)
215.数组中的第K个最大元素题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/kth-largest-element-in-an-array题目在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素... 查看详情
215.数组中的第k个最大元素(代码片段)
算法记录LeetCode题目： 给定整数数组nums和整数k，请返回数组中第k个最大的元素。 请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。思路算法记录说明一、题目二、分析总结... 查看详情
数组中第k大的数（leetcode215）(代码片段)
文章目录1.问题描述2.难度等级3.热门指数4.解题思路5.实现示例5.1C++5.2Golang参考文献1.问题描述给定整数数组nums和整数k，请返回数组中第k个最大的元素。示例1:输入:[3,2,1],k=1输出:3示例2:输入:[3,2,1,5,6,4],k=2输出:5示... 查看详情
数组中第k大的数（leetcode215）(代码片段)
文章目录1.问题描述2.难度等级3.热门指数4.解题思路5.实现示例5.1C++5.2Golang参考文献1.问题描述给定整数数组nums和整数k，请返回数组中第k个最大的元素。示例1:输入:[3,2,1],k=1输出:3示例2:输入:[3,2,1,5,6,4],k=2输出:5示... 查看详情
leetcode刷题100天—215.数组中的第k个最大元素(优先队列)—day15(代码片段)
前言：作者：神的孩子在歌唱大家好，我叫运智给定整数数组nums和整数k，请返回数组中第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。示例1:输入:[3,2,1,... 查看详情
[leetcode]215.数组中的第k个最大元素(堆)(代码片段)
...以假设k总是有效的，且1≤k≤数组的长度。来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/kt 查看详情
leetcode.215-数组中的第k个最大元素(代码片段)
题目在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。示例??输入：[3,2,3,1,2,4,5,5,6]和k=4??输出：4TopK问题是一道高频面试题！解法一：排序+查找由于数组是... 查看详情
leetcode215.数组中的第k个最大元素(快速排序)(代码片段)
...假设k总是有效的，且1≤k≤数组的长度。来源：力扣（LeetCode）链接：https://leetcode-cn.com/pr 查看详情
leetcode215.数组中的第k个最大元素(代码片段)
题目在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。示例1:输入:[3,2,1,5,6,4]和k=2输出:5示例2:输入:[3,2,3,1,2,4,5,5,6]和k=4输出:4解法一：用快排partition思路classS... 查看详情
leetcode215.数组中的第k个最大元素bypython(代码片段)
在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。示例1:输入:[3,2,1,5,6,4]和k=2输出:5示例2:输入:[3,2,3,1,2,4,5,5,6]和k=4输出:4思路一个sorted再直接返回第K个最大... 查看详情
leetcode|215.数组中的第k个最大元素(代码片段)
原题（Medium）： 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。 说明: 你可以假设k总是有效的，且1≤k≤数组的长度。 思路：... 查看详情
leetcode215.数组中的第k个最大元素（kthlargestelementinanarray）(代码片段)
题目描述 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。示例1:输入:[3,2,1,5,6,4]和k=2输出:5示例 2:输入:[3,2,3,1,2,4,5,5,6]和k=4输出:4说明:你... 查看详情
215.数组中的第k个最大元素(代码片段)
...假设k总是有效的，且1≤k≤数组的长度。来源：力扣（LeetCode）链接：https://leetcode-cn.com/pr 查看详情
leetcode笔记215.数组中的第k个最大元素
题目描述题目链接：https://leetcode-cn.com/probl...在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。示例1：输入:[3,2,1,5,6,4]和k=2输出:5示例2：输入:[3,2,3,1,2,4,5,5,6... 查看详情