在未排序的数组中找到第 k 个最大的元素
程序员文章站
2022-03-23 11:29:42
一、引言昨儿面试中遇到的算法题 :在未排序的数组中找到第 k 个最大的元素。首先想到的就是先排序,但是就算是快排的时间复杂度也要O(nlogn),给的时间有限,一时间也没想出更好的办法,想着既然时间复杂度降不下来,那不如就用简单点的堆排序: //大根堆 O(nlogk) public int findKthLargest(int[] nums, int k){ PriorityQueue maxHeap = new PriorityQueue...
一、引言
昨儿面试中遇到的算法题 :在未排序的数组中找到第 k 个最大的元素。首先想到的就是先排序,但是就算是快排的时间复杂度也要O(nlogn),给的时间有限,一时间也没想出更好的办法,想着既然时间复杂度降不下来,那不如就用简单点的堆排序:
//大根堆 O(nlogk)
public int findKthLargest(int[] nums, int k){
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((n1, n2) -> n1-n2);
for (int n: nums){
maxHeap.add(n);
if (maxHeap.size()>k){
maxHeap.poll();
}
}
return maxHeap.poll();
}
结果显然,面试官不是很满意,最后给的建议也是说算法有点弱,确实最近忙着实习,算法题没怎么刷,生疏了。所以趁热打铁,反思的同时,这道题的较优解还是很巧妙的,特此记录。
二、正文
基于快速排序的选择方法
- 思路:
快速排序,是一个典型的分治算法
通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
结合快排,对子数组进行划分,如果划分得到的值正好就是我们需要的下标,就直接返回a[q];否则,如果 q 比目标下标小,就递归右子区间,否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间,提高了时间效率。这就是「快速选择」算法。
- 代码:
Random random = new Random();
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
int left = 0;
int right = len - 1;
// 转换一下,第 k 大元素的索引是 len - k
int target = len - k;
while (true) {
//int i = random.nextInt(right - left + 1) + l;
//swap(a, i, r);
int index = partition(nums, left, right);
if (index == target) {
return nums[index];
} else if (index < target) {
left = index + 1;
} else {
right = index - 1;
}
}
}
//辅助函数,把比轴值大的元素放右边,比轴值小的元素放左边,返回轴值下标
public int partition(int[] nums, int left, int right) {
int pivot = nums[left];
int j = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] < pivot) {
// 小于 pivot 的元素都被交换到前面
j++;
swap(nums, j, i);
}
}
// 在之前遍历的过程中,满足 [left + 1, j] < pivot,并且 (j, i] >= pivot
swap(nums, j, left);
// 交换以后 [left, j - 1] < pivot, nums[j] = pivot, [j + 1, right] >= pivot
return j;
}
//交换
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
时间复杂度:O(N),这里 N 是数组的长度,需要使用主定理进行分析。
空间复杂度:O(1),原地排序,没有借助额外的辅助空间。
另外,为了应对极端测试用例,随机初始化 pivot 元素,随机交换第 1个元素与它后面的任意 1 个元素的位置;最极端的是顺序数组与倒序数组,此时递归树画出来是链表,时间复杂度是 O(N^2),根本达不到减治的效果。
本文地址:https://blog.csdn.net/qq_44543551/article/details/107327322
推荐阅读
-
python数组中的第K个最大元素(快排与堆排)
-
在排序数组中查找元素的第一个和最后一个位置、变形二分法
-
#leetcode刷题之路34-在排序数组中查找元素的第一个和最后一个位置
-
34. 在排序数组中查找元素的第一个和最后一个位置
-
Leetcode No.34 在排序数组中查找元素的第一个和最后一个位置
-
Java算法(递归):两个不同长度的有序数组求第k小的元素(时间复杂度为:O(log(m1 + m2)))。
-
在未排序的数组中找到第 k 个最大的元素
-
获取一个数组里面第K大的元素
-
在排序数组中查找元素的第一个和最后一个位置(二分、lower_bound、upper_bound)
-
在排序数组中查找元素的第一个和最后一个位置