个人卖货入驻什么平台,通过关键词优化提升企业网站,福州建设网站效果图,内容营销价值我本人是非科班学 C 后端和嵌入式的。在我面试的过程中#xff0c;竟然得到了阿里 C 研发工程师的面试机会。因为#xff0c;阿里主要是用 Java 比较多#xff0c;C 的岗位比较少#xff0c;所以感觉这个机会还是挺难得的。
阿里 C 研发工程师面试考了我一道类似于快速…我本人是非科班学 C 后端和嵌入式的。在我面试的过程中竟然得到了阿里 C 研发工程师的面试机会。因为阿里主要是用 Java 比较多C 的岗位比较少所以感觉这个机会还是挺难得的。
阿里 C 研发工程师面试考了我一道类似于快速排序算法的算法题虽然我算法题又一次没做出来然后面试挂了。 题目描述
题号215 给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 解题思路
思路一快排变体快速选择
快速选择算法这是快速排序算法的一种变种。快速选择算法可以在平均情况下以O(n)的时间复杂度找到数组中的第k个最小或最大元素。 步骤如下 选择一个基准元素我们可以随机选择一个元素作为基准或者选择数组的第一个、最后一个或中间的元素。 分区根据基准元素对数组进行分区使得所有小于基准的元素都在基准的左边所有大于基准的元素都在基准的右边。 判断基准元素的位置如果基准元素正好是第k个最大的元素从0开始计数则直接返回该元素。如果基准元素的位置大于k则在基准的左边部分继续寻找如果基准元素的位置小于k则在基准的右边部分继续寻找并调整k的值。 递归在选定的部分中重复上述步骤直到找到第k个最大的元素。 时间复杂度O(N)
空间复杂度O(log N) C
// C
class Solution {
public:int quickselect(vectorint 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(vectorint 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)}
}
