热门

最新

红包

立Flag

投票

同城

发布
wzh18907434168
Eliooooooo
2 年前
truewzh18907434168

每日一题
215. 数组中的第K个最大元素

给定整数数组 `nums` 和整数 `k`，请返回数组中第 `**k**` 个最大的元素。

请注意，你需要找的是数组排序后的第 `k` 个最大的元素，而不是第 `k` 个不同的元素。

你必须设计并实现时间复杂度为 `O(n)` 的算法解决此问题。



**示例 1:**

```
输入: [3,2,1,5,6,4], k = 2
输出: 5

解法一：快速选择

时间复杂度：O(n)

空间复杂度：O(1)
class Solution {
public:
int quickselect(vector<int> &nums, int l, int r, int k) {
if (l == r) return nums[l];
int left = l - 1, right = r + 1;
int key = nums[rand() % (r - l + 1) + l];
for(int i = l; i < right;)
{
if(key < nums[i]) swap(nums[i], nums[--right]);
else if(key > nums[i]) swap(nums[i++], nums[++left]);
else i++;
}
int c = r - right + 1, b = right - left - 1;
if(k <= c) return quickselect(nums, right, r, k);
else if(k <= c + b) return key;
else return quickselect(nums, l, left, k - c - b);
}

int findKthLargest(vector<int> &nums, int k) {
srand(time(NULL));
return quickselect(nums, 0, nums.size() - 1, k);
}
};
每日学习打卡
2
1
打赏
  • 复制链接
  • 举报
下一条：
每日一题912. 排序数组给你一个整数数组 `nums`，请你将该数组升序排列。**示例 1：**```输入：nums = [5,2,3,1]输出：[1,2,3,5]```**示例 2：**```输入：nums = [5,1,1,2,0,0]输出：[0,0,1,1,2,5]```解法一：快排时间复杂度：O(nlogn)空间复杂度：O(1)class Solution {public: vector<int> sortArray(vector<int>& nums) { srand(time(NULL)); quick_sort(nums, 0, nums.size() - 1); return nums; } void quick_sort(vector<int>& arr, int l, int r) { if(l >= r) return; int key = arr[rand() % (r - l + 1) + l]; int left = l - 1, right = r + 1; for(int i = l; i < right; ) { if(arr[i] > key) swap(arr[i], arr[--right]); else if(arr[i] < key) swap(arr[i++], arr[++left]); else i++; } quick_sort(arr, l, left); quick_sort(arr, right, r); }};