题解 | 寻找第K大
寻找第K大
https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
class Solution {
public:
int partition(vector<int>& a, int left, int right) {
int pivot = a[left];
int i = left, j = right;
while (i < j) {
while (i < j && a[j] <= pivot) j--;
a[i] = a[j];
while (i < j && a[i] >= pivot) i++;
a[j] = a[i];
}
a[i] = pivot;
return i;
}
int findKth(vector<int>& a, int n, int K) {
int left = 0, right = n - 1;
while (left <= right) {
int pos = partition(a, left, right);
int len_left = pos - left + 1;
if (len_left == K) {
return a[pos];
} else if (len_left > K) {
right = pos - 1;
} else {
K -= len_left;
left = pos + 1;
}
}
return -1;
}
};
len_left计算左侧部分的元素个数（包括基准值） 情况1：找到目标 如果左侧长度正好等于K，说明基准值就是第K大的元素 直接返回 a[pos] 情况2：目标在左侧 如果左侧长度大于K，说明第K大的元素在左侧部分 缩小搜索范围到左侧：right = pos - 1 情况3：目标在右侧 如果左侧长度小于K，说明第K大的元素在右侧部分 调整K值：K -= len_left（因为我们已经找到了前len_left个最大的元素） 缩小搜索范围到右侧：left = pos + 1
栈/堆/队列 文章被收录于专栏
操作只能在栈顶进行 栈应用场景 函数调用栈 浏览器前进后退 括号匹配检查 表达式求值 变种队列 双端队列 (Deque)：两端都可以入队和出队 优先队列 (Priority Queue)：按优先级出队 循环队列：固定大小的循环使用空间 队列应用场景 消息队列 任务调度 广度优先搜索 打印任务队列 堆应用场景 优先队列实现 堆排序 Top K 问题 定时任务调度
