Leetcode 158 数组中的第K个最大元素 | 查找和最小的 K 对数字

1 题目215. 数组中的第K个最大元素给定整数数组nums和整数k请返回数组中第k个最大的元素。请注意你需要找的是数组排序后的第k个最大的元素而不是第k个不同的元素。你必须设计并实现时间复杂度为O(n)的算法解决此问题。示例 1:输入:[3,2,1,5,6,4],k 2输出:5示例 2:输入:[3,2,3,1,2,4,5,5,6],k 4输出:4提示1 k nums.length 105-104 nums[i] 1042 代码实现cclass Solution { public: int findKthLargest(vectorint nums, int k) { priority_queueint , vectorint ,greaterint minHeap ; for (int num : nums){ minHeap.push(num); if(minHeap.size() k ){ minHeap.pop(); } } return minHeap.top(); } };jsvar findKthLargest function(nums, k) { // 最小堆 class MinHeap { constructor() { this.heap []; } push(val) { this.heap.push(val); this.bubbleUp(this.heap.length - 1); } pop() { const min this.heap[0]; const last this.heap.pop(); if (this.heap.length 0) { this.heap[0] last; this.bubbleDown(0); } return min; } top() { return this.heap[0]; } size() { return this.heap.length; } bubbleUp(idx) { while (idx 0) { const parent (idx - 1) 1; if (this.heap[parent] this.heap[idx]) break; [this.heap[parent], this.heap[idx]] [this.heap[idx], this.heap[parent]]; idx parent; } } bubbleDown(idx) { const len this.heap.length; while (true) { let left idx * 2 1; let right idx * 2 2; let smallest idx; if (left len this.heap[left] this.heap[smallest]) smallest left; if (right len this.heap[right] this.heap[smallest]) smallest right; if (smallest idx) break; [this.heap[idx], this.heap[smallest]] [this.heap[smallest], this.heap[idx]]; idx smallest; } } } const heap new MinHeap(); for (let num of nums) { heap.push(num); if (heap.size() k) heap.pop(); } return heap.top(); };思考完了只会想到要用sort各种排序算法其实我也都不会啊完蛋了题解先搞懂 2 个核心问题1. 我们要找什么第 k 个最大元素比如数组[3,2,1,5,6,4]k2排序后[1,2,3,4,5,6]最大的 2 个数是6、5→第 2 大就是 5也就是说我们只要保留数组里最大的 k 个数这里面最小的那个就是第 k 大元素2. 为什么用「小顶堆」堆有两种大顶堆堆顶是最大的小顶堆堆顶是最小的我们用小顶堆理由超简单维护一个大小固定为 k的小顶堆堆里只存当前最大的 k 个数堆顶 这 k 个数里最小的 →就是答案完整思路一步一步走创建一个小顶堆大小最多 k遍历数组里每一个数字堆没满 → 直接放进去堆满了如果当前数比堆顶大→ 删掉堆顶把新数加进去如果比堆顶小 → 跳过遍历结束堆顶就是第 k 大元素举个例子秒懂数组[3,2,1,5,6,4]k23 → 堆空加入 → 堆[3]2 → 堆没满加入 → 堆[2,3]堆顶是 21 → 比 2 小 → 跳过5 → 比 2 大 → 删 2加 5 → 堆[3,5]堆顶 36 → 比 3 大 → 删 3加 6 → 堆[5,6]堆顶 54 → 比 5 小 → 跳过最终堆顶 5→ 正确答案C 代码#include iostream #include vector #include queue // 用优先队列实现堆 using namespace std; class Solution { public: int findKthLargest(vectorint nums, int k) { // 关键行 // 小顶堆堆顶永远是堆内最小元素 // priority_queue 默认是大顶堆加上 greaterint 变成小顶堆 priority_queueint, vectorint, greaterint minHeap; // 遍历数组所有数字 for (int num : nums) { // 先把当前数放进堆 minHeap.push(num); // 核心规则 // 如果堆的大小 超过 k就把最小的堆顶删掉 if (minHeap.size() k) { minHeap.pop(); } } // 最后堆顶 最大的 k 个数里最小的 第 k 大元素 return minHeap.top(); } }; // 测试 int main() { vectorint nums1 {3,2,1,5,6,4}; cout Solution().findKthLargest(nums1, 2) endl; // 输出 5 vectorint nums2 {3,2,3,1,2,4,5,5,6}; cout Solution().findKthLargest(nums2, 4) endl; // 输出 4 }最关键的 3 行代码背下来// 1. 创建小顶堆 priority_queueint, vectorint, greaterint minHeap; // 2. 插入元素 minHeap.push(num); // 3. 超过 k 大小就弹出最小的 if (minHeap.size() k) minHeap.pop();时间 空间复杂度时间复杂度O (n log k)每个元素入堆出堆是 log k一共 n 个元素题目要求 O (n)但这个方法面试 100% 能过代码极短、不容易写错空间复杂度O (k)只维护大小为 k 的堆你必须记住的总结超简单找第 k 大 → 用小顶堆堆大小固定为 k比堆顶大就替换小就跳过最后堆顶就是答案3 题目373. 查找和最小的 K 对数字给定两个以非递减顺序排列的整数数组nums1和nums2, 以及一个整数k。定义一对值(u,v)其中第一个元素来自nums1第二个元素来自nums2。请找到和最小的k个数对(u1,v1),(u2,v2)...(uk,vk)。示例 1:输入:nums1 [1,7,11], nums2 [2,4,6], k 3输出:[[1,2],[1,4],[1,6]]解释:返回序列中的前 3 对数 [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]示例 2:输入:nums1 [1,1,2], nums2 [1,2,3], k 2输出:[[1,1],[1,1]]解释:返回序列中的前 2 对数 [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]提示:1 nums1.length, nums2.length 105-109 nums1[i], nums2[i] 109nums1和nums2均为升序排列1 k 104k nums1.length * nums2.length4 代码实现c#include vector #include queue #include set using namespace std; class Solution { public: vectorvectorint kSmallestPairs(vectorint nums1, vectorint nums2, int k) { // 小顶堆存储 {sum, i, j} priority_queuevectorint, vectorvectorint, greatervectorint pq; // 去重记录已经加入堆的下标对 (i,j) setpairint, int visited; vectorvectorint res; // 初始化最小和一定是 nums1[0]nums2[0] pq.push({nums1[0] nums2[0], 0, 0}); visited.insert({0, 0}); // 取 k 次 while (k-- 0 !pq.empty()) { auto cur pq.top(); pq.pop(); int sum cur[0]; int i cur[1]; int j cur[2]; // 加入答案 res.push_back({nums1[i], nums2[j]}); // 往下走i1, j if (i 1 nums1.size() !visited.count({i1, j})) { pq.push({nums1[i1] nums2[j], i1, j}); visited.insert({i1, j}); } // 往右走i, j1 if (j 1 nums2.size() !visited.count({i, j1})) { pq.push({nums1[i] nums2[j1], i, j1}); visited.insert({i, j1}); } } return res; } };jsvar kSmallestPairs function(nums1, nums2, k) { // ------------- 手写 最小堆和上一题完全一样------------- class MinHeap { constructor() { this.heap []; } push(val) { this.heap.push(val); this.bubbleUp(this.heap.length - 1); } pop() { const min this.heap[0]; const last this.heap.pop(); if (this.heap.length) { this.heap[0] last; this.bubbleDown(0); } return min; } top() { return this.heap[0]; } size() { return this.heap.length; } bubbleUp(idx) { while (idx 0) { const p (idx - 1) 1; if (this.heap[p][0] this.heap[idx][0]) break; [this.heap[p], this.heap[idx]] [this.heap[idx], this.heap[p]]; idx p; } } bubbleDown(idx) { const len this.heap.length; while (true) { let l idx * 2 1, r idx * 2 2, s idx; if (l len this.heap[l][0] this.heap[s][0]) s l; if (r len this.heap[r][0] this.heap[s][0]) s r; if (s idx) break; [this.heap[idx], this.heap[s]] [this.heap[s], this.heap[idx]]; idx s; } } } // ------------- 正式逻辑 ------------- const heap new MinHeap(); const visited new Set(); // 防止重复加入 const res []; // 初始把第0行0列放进去 heap.push([nums1[0] nums2[0], 0, 0]); visited.add(0,0); // 取 k 次 while (k-- 0 heap.size() 0) { // 取出当前最小和 const [sum, i, j] heap.pop(); res.push([nums1[i], nums2[j]]); // 往下走i1, j if (i 1 nums1.length !visited.has(${i1},${j})) { heap.push([nums1[i1] nums2[j], i1, j]); visited.add(${i1},${j}); } // 往右走i, j1 if (j 1 nums2.length !visited.has(${i},${j1})) { heap.push([nums1[i] nums2[j1], i, j1]); visited.add(${i},${j1}); } } return res; };思考好难。。。。不会做。。。题解一、核心思路和刚才完全一样不变两个升序数组找和最小的 k 个数对用小顶堆每次弹出最小和堆里存{两数之和, 数组1下标, 数组2下标}用set / 二维数组记录已经加入堆的下标对防止重复取出 k 次堆顶就是答案二、C 重点知识必须知道C 默认优先队列是大顶堆想变成小顶堆必须这么写priority_queuevectorint, vectorvectorint, greatervectorint pq;堆会自动按第一个元素和从小到大排序三、C 完整代码#include vector #include queue #include set using namespace std; class Solution { public: vectorvectorint kSmallestPairs(vectorint nums1, vectorint nums2, int k) { // 小顶堆存储 {sum, i, j} priority_queuevectorint, vectorvectorint, greatervectorint pq; // 去重记录已经加入堆的下标对 (i,j) setpairint, int visited; vectorvectorint res; // 初始化最小和一定是 nums1[0]nums2[0] pq.push({nums1[0] nums2[0], 0, 0}); visited.insert({0, 0}); // 取 k 次 while (k-- 0 !pq.empty()) { auto cur pq.top(); pq.pop(); int sum cur[0]; int i cur[1]; int j cur[2]; // 加入答案 res.push_back({nums1[i], nums2[j]}); // 往下走i1, j if (i 1 nums1.size() !visited.count({i1, j})) { pq.push({nums1[i1] nums2[j], i1, j}); visited.insert({i1, j}); } // 往右走i, j1 if (j 1 nums2.size() !visited.count({i, j1})) { pq.push({nums1[i] nums2[j1], i, j1}); visited.insert({i, j1}); } } return res; } };四、代码逐行解释超级简单小顶堆定义priority_queuevectorint, vectorvectorint, greatervectorint pq;存储格式{两数之和, nums1下标i, nums2下标j}去重 setsetpairint, int visited;防止同一个(i,j)被多次加入堆初始化最小和一定是第一个数对(0,0)循环 k 次每次弹出堆顶最小和加入答案把下面 (i1,j)和右边 (i,j1)加入堆标记已访问返回结果存的就是前 k 小和数对五、测试示例// 示例1 nums1 [1,7,11], nums2 [2,4,6], k3 输出[[1,2],[1,4],[1,6]] // 示例2 nums1 [1,1,2], nums2 [1,2,3], k2 输出[[1,1],[1,1]]六、你只需要记住 4 句话找最小 k 个 → 小顶堆堆存{sum, i, j}每次取堆顶加入答案向下、向右扩展用 set 去重5 小结不知道怎么搞我觉得非常难先混过去了非常难第一题在hot 100 要会后面都随意写一些。