鹰潭网站建设公司_公司主页是什么_站长工具百科_seo技术培训

我本人是非科班学 C++ 后端和嵌入式的。在我面试的过程中，竟然得到了阿里​ C++ 研发工程师的面试机会。因为，阿里主要是用 Java 比较多，C++ 的岗位比较少​，所以感觉这个机会还是挺难得的。

阿里 C++ 研发工程师面试考了我一道类似于快速排序算法的算法题，虽然我算法题又一次没做出来然后面试挂了。

题目描述：

题号：215

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

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

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

解题思路：

思路一：快排变体（快速选择）

快速选择算法，这是快速排序算法的一种变种。快速选择算法可以在平均情况下以O(n)的时间复杂度找到数组中的第k个最小（或最大）元素。

步骤如下：

1. 选择一个基准元素：我们可以随机选择一个元素作为基准，或者选择数组的第一个、最后一个或中间的元素。

2. 分区：根据基准元素对数组进行分区，使得所有小于基准的元素都在基准的左边，所有大于基准的元素都在基准的右边。

3. 判断基准元素的位置：如果基准元素正好是第k个最大的元素（从0开始计数），则直接返回该元素。如果基准元素的位置大于k，则在基准的左边部分继续寻找；如果基准元素的位置小于k，则在基准的右边部分继续寻找，并调整k的值。

4. 递归：在选定的部分中重复上述步骤，直到找到第k个最大的元素。

时间复杂度：O(N) 

空间复杂度：O(log N)

C++

// C++
class Solution {
public:int quickselect(vector<int> &nums, int l, int r, int k) {if (l == r)return nums[k];int partition = nums[l], i = l - 1, j = r + 1;while (i < j) {do i++; while (nums[i] < partition);do j--; while (nums[j] > partition);if (i < j)swap(nums[i], nums[j]);}if (k <= j)return quickselect(nums, l, j, k);else return quickselect(nums, j + 1, r, k);}
​int findKthLargest(vector<int> &nums, int k) {int n = nums.size();return quickselect(nums, 0, n - 1, n - k);}
};

go

// go
func findKthLargest(nums []int, k int) int {n := len(nums)return quickselect(nums, 0, n - 1, n - k)
}
​
func quickselect(nums []int, l, r, k int) int{if (l == r){return nums[k]}partition := nums[l]i := l - 1j := r + 1for (i < j) {for i++;nums[i]<partition;i++{}for j--;nums[j]>partition;j--{}if (i < j) {nums[i],nums[j]=nums[j],nums[i]}}if (k <= j){return quickselect(nums, l, j, k)}else{return quickselect(nums, j + 1, r, k)}
}