Kth Largest Element in an Array Leetcode #215 题解[C++]
程序员文章站
2022-04-25 13:32:56
...
题目来源
https://leetcode.com/problems/kth-largest-element-in-an-array/description/
题目理解
ind the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4]
and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
找出给定数组中第 k 大的元素. 假定 k 总是合法的.
解题思路
这道题相信能够直接看出最简单粗暴的解法, 即使用快速排序先将数组排好序, 再直接找出第 k 大的元素.
但回想一下快速排序的过程, 我们完全可以在这个基础上进行优化. 注意到, 每趟快排都会有一个分区的过程, 在这个过程里, 我们可以直接判断第 k 大的数会落在哪一边, 进而只对一边进行再查找, 就能够节省将近一半的工作量. ( 平均情形 )
代码实现
这段代码在时间排序上表现比较一般, 这一方面是因为这道题中许多人直接用了标准库中的make_heap, sort, dequeue
等手段, 算是走了捷径; 另一个原因是我用的快排版本是方便记忆的和理解的, 并不是较快版本的快排.
#include <iostream>
#include <vector>
using namespace std;
#include <iostream>
using namespace std;
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return recursiveFind(0, nums.size() - 1, nums.size()-k,nums);
}
int recursiveFind(int left, int right, int k, vector<int>&nums) {
int lo = left;
int hi = right;
int key = nums[lo];
while (lo < hi) {
while (lo < hi&&nums[hi] >= key) --hi;
nums[lo] = nums[hi];
while (lo < hi&&nums[lo] <= key) ++lo;
nums[hi] = nums[lo];
}
nums[lo] = key;
if (k == lo) return nums[lo];
else if (k > lo) return recursiveFind(lo + 1, right, k, nums);
else return recursiveFind(left, lo - 1, k, nums);
}
};
下一篇: 用addRoutes实现动态路由
推荐阅读
-
Kth Largest Element in an Array Leetcode #215 题解[C++]
-
215. Kth Largest Element in an Array
-
LeetCode 215 Kth Largest Element in an Array
-
LeetCode 215. Kth Largest Element in an Array
-
LeetCode算法问题14 —— Kth Largest Element in an Array
-
215. Kth Largest Element in an Array(返回数组中第几大元素)(leetcode)
-
LeetCode 215 -- 数组中的第K个最大元素 ( Kth Largest Element in an Array ) ( C语言版 )
-
215[Medium]:Kth Largest Element in an Array
-
leetcode215:Kth Largest Element in an Array
-
[email protected]_215_Kth_Largest_Element_in_an_Array