最小的 k 个数面试题 17.14. 最小K个数设计一个算法找出数组中最小的 k 个数。以任意顺序返回这 k 个数均可。示例输入 arr [1,3,5,7,2,4,6,8], k 4 输出 [1,2,3,4]提示0 len(arr) 1000000 k min(100000, len(arr))快速选择算法分治利用快速排序恰好有 「左侧元素」 小于等于 「基准值」「右侧元素」 大于 「基准值」 的特性我们可以基于快速排序算法划分数组也成为快速选择。注意任意顺序是核心否则不能使用快速选择算法。// 注意到题目要求「任意顺序返回这 k 个数即可」因此我们只需要确保前 k 小的数都出现在下标为 [0,k) 的位置即可。// 而快速排序恰好有 「左侧元素」 小于等于 「基准值」「右侧元素」 大于 「基准值」 的特性因此我们可以利用快速排序划分数组// 在面试中如果面试官追加一句“如果是 100 亿个数据内存放不下怎么办”这时候就必须用堆了。// 我们只要维护一个容量为 k 的大根堆新来的元素如果比堆顶小就把堆顶踢掉自己进去。时间复杂度是 O(Nlogk)。classSolution{// void quick_select(vectorint arr, int target_index, int l, int r) {// if(l r) return ;// int pivot arr[(l r) / 2];// int i l - 1, j r 1;// while(i j) {// do i ; while(arr[i] pivot);// do j -- ; while(arr[j] pivot);// if(i j) swap(arr[i], arr[j]);// }// if(j target_index) quick_select(arr, target_index, l, j);// if(j 1 target_index) quick_select(arr, target_index, j 1, r);// }voidquick_select(vectorintarr,inttarget_index,intl,intr){if(lr)return;intpivotarr[(lr1)/2];intil-1,jr1;while(ij){doi;while(arr[i]pivot);doj--;while(arr[j]pivot);if(ij)swap(arr[i],arr[j]);}if(i-1target_index)quick_select(arr,target_index,l,i-1);if(itarget_index)quick_select(arr,target_index,i,r);}// 注意如果我们使用随机数生成 pivot最好使用 j 作为边界而不是 ipublic:vectorintsmallestK(vectorintarr,intk){if(k0)return{};if(karr.size())returnarr;quick_select(arr,k-1,0,arr.size()-1);returnvectorint(arr.begin(),arr.begin()k);}};时间复杂度平均O ( N ) O(N)O(N)。因为每次划分大概能排除掉一半的数据计算量递减N N / 2 N / 4 ⋯ ≈ 2 N N N/2 N/4 \dots \approx 2NNN/2N/4⋯≈2N。最坏情况是数组已经有序每次只排除一个元素会退化到O ( N 2 ) O(N^2)O(N2)实际工程中通常会引入随机挑选基准来避免这种极端情况。空间复杂度平均O ( log N ) O(\log N)O(logN)。主要开销来自递归调用的函数栈深度。最坏情况下时间退化的同时递归树变成一条直线空间复杂度退化为O ( N ) O(N)O(N)。什么时候用堆排序在面试中如果面试官追加一句“如果是 100 亿个数据内存放不下怎么办”这时候就必须用堆了。我们只要维护一个容量为k kk的大根堆新来的元素如果比堆顶小就把堆顶踢掉自己进去。时间复杂度是O ( N log k ) O(N \log k)O(Nlogk)。第 k 个数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] 104快速选择算法分治// 快速选择算法 O(n) O(n)intfindKthLargest(vectorintnums,intk){// 由于我们后面需要 % nums.size()// 因此这里要确保 nums.size() 不为 0if(!nums.size())return0;vectorintsmall,equal,big;intpivotnums[rand()%nums.size()];for(autox:nums){if(xpivot)equal.push_back(x);elseif(xpivot)big.push_back(x);elsesmall.push_back(x);}if(kbig.size())returnfindKthLargest(big,k);if(kbig.size()equal.size())returnpivot;returnfindKthLargest(small,k-(big.size()equal.size()));}计数排序// 计数排序 O(n) O(n)intfindKthLargest_1(vectorintnums,intk){knums.size()-k1;intlINT_MAX,rINT_MIN;unordered_mapint,intcnt;for(autox:nums){cnt[x];lmin(l,x);rmax(r,x);}for(intil;ir;i){if((k-cnt[i])0)returni;}// never go therereturnINT_MAX;}第 k 个数拓展4. 寻找两个正序数组的中位数给定两个大小分别为m和n的正序从小到大数组nums1和nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log (mn))。示例 1输入nums1 [1,3], nums2 [2] 输出2.00000 解释合并数组 [1,2,3] 中位数 2示例 2输入nums1 [1,2], nums2 [3,4] 输出2.50000 解释合并数组 [1,2,3,4] 中位数 (2 3) / 2 2.5提示nums1.length mnums2.length n0 m 10000 n 10001 m n 2000-106 nums1[i], nums2[i] 106分治 递归这道题的意思其实很简单就是让我们求两个数组的中位数。我们假设我们已经将两个数组排序成一个长度为nm的数组那么当nm为奇数时求第n 2 \frac{n}{2}2n个元素当nm为偶数时求第n − 1 2 \frac{n-1}{2}2n−1和第n 2 \frac{n}{2}2n个元素取平均注意都是下取整那么其实我们就把问题转换为了求第k kk小数只不过相较于朴素的第 k 小数这里我们要在两个有序数组中找到第k kk小的数。我们可以基于这样的思想每次排除掉k 2 \frac{k}{2}2k个元素直到最后只剩一个元素。// REF:windliang// 在两个有序数组中求第 k 小数每次排除掉 k/2 个元素k-k/2classSolution{// 在两个有序数组中求第 k 小数doublerecursion(vectorintnums1,intl1,intr1,vectorintnums2,intl2,intr2,intk){// 放了方便处理数组为空的情况我们总是令 nums1 的长度大于等于 nums2 的长度if(r2-l2r1-l1)returnrecursion(nums2,l2,r2,nums1,l1,r1,k);// 递归结束条件if(l2r2)returnnums1[l1k-1];if(k1)returnmin(nums1[l1],nums2[l2]);// 每次排除掉 k/2 个元素注意 nums2 可能不够 k/2 个元素但 nums1 一定有 k/2 个元素不做证明intcnt1min(k/2,r1-l11);intcnt2min(k/2,r2-l21);// 子递归if(nums1[l1cnt1-1]nums2[l2cnt2-1])returnrecursion(nums1,l1cnt1,r1,nums2,l2,r2,k-cnt1);// 抛弃掉 nums1[l1, l1 cnt1 - 1] 共 cnt1 个元素returnrecursion(nums1,l1,r1,nums2,l2cnt2,r2,k-cnt2);// 抛弃掉 nums2[l2, l2 cnt2 - 1] 共 cnt2 个元素}public:doublefindMedianSortedArrays(vectorintnums1,vectorintnums2){// 我们这里规定第 1 小数对应 arr[0]即数组下标从 0 开始// 0 1 (2) 3 4 - idxsize/25/22 - a[idx]// 0 1 (2) (3) 4 5 - idxsize/26/23 - (a[idx-1] a[idx]) / 2intnnums1.size(),mnums2.size();intidx(nm)/2;// 注意由数组下标 idx 转换为 k 需要 1即 kidx1if((nm)1)returnrecursion(nums1,0,n-1,nums2,0,m-1,idx1);return(recursion(nums1,0,n-1,nums2,0,m-1,idx)recursion(nums1,0,n-1,nums2,0,m-1,idx1))/2.0;}};时间复杂度O ( l o g ( m n ) ) O(log(mn))O(log(mn))咱们的核心逻辑是“找第k小的数”。每次递归都会对比并精准淘汰掉k/2 个绝对不可能的元素。这相当于每次都把查找范围暴力缩小一半。因为k的初始值差不多是总长度的一半这种不断“折半砍”的动作执行次数也就是 log(mn) 级别。空间复杂度O ( l o g ( m n ) ) O(log(mn))O(log(mn))代码里咱们全程都是拿着索引l1、r1等在原数组上比对没有新建任何数组或哈希表。唯一的内存消耗来自递归调用时产生的系统函数栈。既然递归往下走了 log(mn) 层栈的深度自然就是O(log(mn))。为什么每次排除掉1 2 \frac{1}{2}21的元素简单来说选k / 2 k/2k/2是为了在**“保证绝对安全”的前提下做到“最极致的效率”**。核心就这 3 点追求二分的速度如果我们每次只比较并排除 1 个元素比如用双指针挨个比那找第k kk个数就要循环k kk次时间复杂度就退化成了龟速的O ( k ) O(k)O(k)。为了满足题目对数级别的要求我们必须像二分查找一样每次把目标范围直接“砍掉一半”。数学上的绝对安全为什么排掉较小的那k / 2 k/2k/2个数绝对不会“误杀”目标假设我们比较了两个数组的第k / 2 k/2k/2个数设为A AA和B BB。如果A B A BAB那么A AA这个数撑死了也只能大于nums1里的k / 2 − 1 k/2 - 1k/2−1个数以及nums2里的k / 2 − 1 k/2 - 1k/2−1个数。加起来总共才k − 2 k-2k−2个数。这意味着A AA充其量也就是全局第k − 1 k-1k−1小的数。所以A AA以及它前面的所有数连成为第k kk小数的资格都没有直接整锅端掉是绝对安全的。为什么不排除更多比如你想一次性排除2 k / 3 2k/32k/3个元素来加速那就无法保证上面的数学推导了你极有可能会把真正的答案给误删掉。k / 2 k/2k/2就是理论上能一口气安全切掉的最大极限。每次切掉一半的k kk这才是真正的“分治”艺术。迭代写法把递归改成迭代也就是用while循环核心思想完全没变只是把函数自己调用自己变成了不断更新指针。这样一来连递归那点系统栈的内存都省了空间复杂度直接干到绝对的O ( 1 ) O(1)O(1)。classSolution{// 迭代版的求第 K 小数doublegetKth(vectorintnums1,vectorintnums2,intk){intmnums1.size(),nnums2.size();// l1 和 l2 相当于两个指针记录两个数组当前还没被淘汰的起始位置intl10,l20;while(true){// 边界情况 1nums1 里的数全被淘汰光了直接去 nums2 里找剩下的第 k 个if(l1m)returnnums2[l2k-1];// 边界情况 2nums2 里的数全被淘汰光了if(l2n)returnnums1[l1k-1];// 边界情况 3k 减到了 1说明下一个就是要找的数直接挑俩指针当前指着的最小值if(k1)returnmin(nums1[l1],nums2[l2]);// 各自往前看 k/2 个元素注意加上当前的偏移量 l1/l2并且千万别越界intidx1min(l1k/2-1,m-1);intidx2min(l2k/2-1,n-1);// 谁的“界碑”小就大胆淘汰谁及它前面的那截元素if(nums1[idx1]nums2[idx2]){// 精准扣减 k 值减去这次实际淘汰的元素个数k-(idx1-l11);// 把 nums1 的指针推到被淘汰元素的下一个位置l1idx11;}else{k-(idx2-l21);l2idx21;}}}public:doublefindMedianSortedArrays(vectorintnums1,vectorintnums2){intnnums1.size(),mnums2.size();inttotalLengthnm;// 奇偶情况拆分复用 getKth 逻辑if(totalLength%21){returngetKth(nums1,nums2,totalLength/21);}else{return(getKth(nums1,nums2,totalLength/2)getKth(nums1,nums2,totalLength/21))/2.0;}}};迭代版的核心变化就这三点循环代替递归用一个while (true)死循环罩住满足边界条件就直接return结果。指针推进之前是靠传递各种l1, r1缩小范围现在只需要维护l1和l2两个起始指针不断向右推相当于逻辑上把左边的元素给“截断”了。内存极简除了几个整型变量什么额外空间都没开辟。
K 小数问题
发布时间：2026/6/21 7:57:03
最小的 k 个数面试题 17.14. 最小K个数设计一个算法找出数组中最小的 k 个数。以任意顺序返回这 k 个数均可。示例输入 arr [1,3,5,7,2,4,6,8], k 4 输出 [1,2,3,4]提示0 len(arr) 1000000 k min(100000, len(arr))快速选择算法分治利用快速排序恰好有 「左侧元素」 小于等于 「基准值」「右侧元素」 大于 「基准值」 的特性我们可以基于快速排序算法划分数组也成为快速选择。注意任意顺序是核心否则不能使用快速选择算法。// 注意到题目要求「任意顺序返回这 k 个数即可」因此我们只需要确保前 k 小的数都出现在下标为 [0,k) 的位置即可。// 而快速排序恰好有 「左侧元素」 小于等于 「基准值」「右侧元素」 大于 「基准值」 的特性因此我们可以利用快速排序划分数组// 在面试中如果面试官追加一句“如果是 100 亿个数据内存放不下怎么办”这时候就必须用堆了。// 我们只要维护一个容量为 k 的大根堆新来的元素如果比堆顶小就把堆顶踢掉自己进去。时间复杂度是 O(Nlogk)。classSolution{// void quick_select(vectorint arr, int target_index, int l, int r) {// if(l r) return ;// int pivot arr[(l r) / 2];// int i l - 1, j r 1;// while(i j) {// do i ; while(arr[i] pivot);// do j -- ; while(arr[j] pivot);// if(i j) swap(arr[i], arr[j]);// }// if(j target_index) quick_select(arr, target_index, l, j);// if(j 1 target_index) quick_select(arr, target_index, j 1, r);// }voidquick_select(vectorintarr,inttarget_index,intl,intr){if(lr)return;intpivotarr[(lr1)/2];intil-1,jr1;while(ij){doi;while(arr[i]pivot);doj--;while(arr[j]pivot);if(ij)swap(arr[i],arr[j]);}if(i-1target_index)quick_select(arr,target_index,l,i-1);if(itarget_index)quick_select(arr,target_index,i,r);}// 注意如果我们使用随机数生成 pivot最好使用 j 作为边界而不是 ipublic:vectorintsmallestK(vectorintarr,intk){if(k0)return{};if(karr.size())returnarr;quick_select(arr,k-1,0,arr.size()-1);returnvectorint(arr.begin(),arr.begin()k);}};时间复杂度平均O ( N ) O(N)O(N)。因为每次划分大概能排除掉一半的数据计算量递减N N / 2 N / 4 ⋯ ≈ 2 N N N/2 N/4 \dots \approx 2NNN/2N/4⋯≈2N。最坏情况是数组已经有序每次只排除一个元素会退化到O ( N 2 ) O(N^2)O(N2)实际工程中通常会引入随机挑选基准来避免这种极端情况。空间复杂度平均O ( log N ) O(\log N)O(logN)。主要开销来自递归调用的函数栈深度。最坏情况下时间退化的同时递归树变成一条直线空间复杂度退化为O ( N ) O(N)O(N)。什么时候用堆排序在面试中如果面试官追加一句“如果是 100 亿个数据内存放不下怎么办”这时候就必须用堆了。我们只要维护一个容量为k kk的大根堆新来的元素如果比堆顶小就把堆顶踢掉自己进去。时间复杂度是O ( N log k ) O(N \log k)O(Nlogk)。第 k 个数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] 104快速选择算法分治// 快速选择算法 O(n) O(n)intfindKthLargest(vectorintnums,intk){// 由于我们后面需要 % nums.size()// 因此这里要确保 nums.size() 不为 0if(!nums.size())return0;vectorintsmall,equal,big;intpivotnums[rand()%nums.size()];for(autox:nums){if(xpivot)equal.push_back(x);elseif(xpivot)big.push_back(x);elsesmall.push_back(x);}if(kbig.size())returnfindKthLargest(big,k);if(kbig.size()equal.size())returnpivot;returnfindKthLargest(small,k-(big.size()equal.size()));}计数排序// 计数排序 O(n) O(n)intfindKthLargest_1(vectorintnums,intk){knums.size()-k1;intlINT_MAX,rINT_MIN;unordered_mapint,intcnt;for(autox:nums){cnt[x];lmin(l,x);rmax(r,x);}for(intil;ir;i){if((k-cnt[i])0)returni;}// never go therereturnINT_MAX;}第 k 个数拓展4. 寻找两个正序数组的中位数给定两个大小分别为m和n的正序从小到大数组nums1和nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log (mn))。示例 1输入nums1 [1,3], nums2 [2] 输出2.00000 解释合并数组 [1,2,3] 中位数 2示例 2输入nums1 [1,2], nums2 [3,4] 输出2.50000 解释合并数组 [1,2,3,4] 中位数 (2 3) / 2 2.5提示nums1.length mnums2.length n0 m 10000 n 10001 m n 2000-106 nums1[i], nums2[i] 106分治 递归这道题的意思其实很简单就是让我们求两个数组的中位数。我们假设我们已经将两个数组排序成一个长度为nm的数组那么当nm为奇数时求第n 2 \frac{n}{2}2n个元素当nm为偶数时求第n − 1 2 \frac{n-1}{2}2n−1和第n 2 \frac{n}{2}2n个元素取平均注意都是下取整那么其实我们就把问题转换为了求第k kk小数只不过相较于朴素的第 k 小数这里我们要在两个有序数组中找到第k kk小的数。我们可以基于这样的思想每次排除掉k 2 \frac{k}{2}2k个元素直到最后只剩一个元素。// REF:windliang// 在两个有序数组中求第 k 小数每次排除掉 k/2 个元素k-k/2classSolution{// 在两个有序数组中求第 k 小数doublerecursion(vectorintnums1,intl1,intr1,vectorintnums2,intl2,intr2,intk){// 放了方便处理数组为空的情况我们总是令 nums1 的长度大于等于 nums2 的长度if(r2-l2r1-l1)returnrecursion(nums2,l2,r2,nums1,l1,r1,k);// 递归结束条件if(l2r2)returnnums1[l1k-1];if(k1)returnmin(nums1[l1],nums2[l2]);// 每次排除掉 k/2 个元素注意 nums2 可能不够 k/2 个元素但 nums1 一定有 k/2 个元素不做证明intcnt1min(k/2,r1-l11);intcnt2min(k/2,r2-l21);// 子递归if(nums1[l1cnt1-1]nums2[l2cnt2-1])returnrecursion(nums1,l1cnt1,r1,nums2,l2,r2,k-cnt1);// 抛弃掉 nums1[l1, l1 cnt1 - 1] 共 cnt1 个元素returnrecursion(nums1,l1,r1,nums2,l2cnt2,r2,k-cnt2);// 抛弃掉 nums2[l2, l2 cnt2 - 1] 共 cnt2 个元素}public:doublefindMedianSortedArrays(vectorintnums1,vectorintnums2){// 我们这里规定第 1 小数对应 arr[0]即数组下标从 0 开始// 0 1 (2) 3 4 - idxsize/25/22 - a[idx]// 0 1 (2) (3) 4 5 - idxsize/26/23 - (a[idx-1] a[idx]) / 2intnnums1.size(),mnums2.size();intidx(nm)/2;// 注意由数组下标 idx 转换为 k 需要 1即 kidx1if((nm)1)returnrecursion(nums1,0,n-1,nums2,0,m-1,idx1);return(recursion(nums1,0,n-1,nums2,0,m-1,idx)recursion(nums1,0,n-1,nums2,0,m-1,idx1))/2.0;}};时间复杂度O ( l o g ( m n ) ) O(log(mn))O(log(mn))咱们的核心逻辑是“找第k小的数”。每次递归都会对比并精准淘汰掉k/2 个绝对不可能的元素。这相当于每次都把查找范围暴力缩小一半。因为k的初始值差不多是总长度的一半这种不断“折半砍”的动作执行次数也就是 log(mn) 级别。空间复杂度O ( l o g ( m n ) ) O(log(mn))O(log(mn))代码里咱们全程都是拿着索引l1、r1等在原数组上比对没有新建任何数组或哈希表。唯一的内存消耗来自递归调用时产生的系统函数栈。既然递归往下走了 log(mn) 层栈的深度自然就是O(log(mn))。为什么每次排除掉1 2 \frac{1}{2}21的元素简单来说选k / 2 k/2k/2是为了在**“保证绝对安全”的前提下做到“最极致的效率”**。核心就这 3 点追求二分的速度如果我们每次只比较并排除 1 个元素比如用双指针挨个比那找第k kk个数就要循环k kk次时间复杂度就退化成了龟速的O ( k ) O(k)O(k)。为了满足题目对数级别的要求我们必须像二分查找一样每次把目标范围直接“砍掉一半”。数学上的绝对安全为什么排掉较小的那k / 2 k/2k/2个数绝对不会“误杀”目标假设我们比较了两个数组的第k / 2 k/2k/2个数设为A AA和B BB。如果A B A BAB那么A AA这个数撑死了也只能大于nums1里的k / 2 − 1 k/2 - 1k/2−1个数以及nums2里的k / 2 − 1 k/2 - 1k/2−1个数。加起来总共才k − 2 k-2k−2个数。这意味着A AA充其量也就是全局第k − 1 k-1k−1小的数。所以A AA以及它前面的所有数连成为第k kk小数的资格都没有直接整锅端掉是绝对安全的。为什么不排除更多比如你想一次性排除2 k / 3 2k/32k/3个元素来加速那就无法保证上面的数学推导了你极有可能会把真正的答案给误删掉。k / 2 k/2k/2就是理论上能一口气安全切掉的最大极限。每次切掉一半的k kk这才是真正的“分治”艺术。迭代写法把递归改成迭代也就是用while循环核心思想完全没变只是把函数自己调用自己变成了不断更新指针。这样一来连递归那点系统栈的内存都省了空间复杂度直接干到绝对的O ( 1 ) O(1)O(1)。classSolution{// 迭代版的求第 K 小数doublegetKth(vectorintnums1,vectorintnums2,intk){intmnums1.size(),nnums2.size();// l1 和 l2 相当于两个指针记录两个数组当前还没被淘汰的起始位置intl10,l20;while(true){// 边界情况 1nums1 里的数全被淘汰光了直接去 nums2 里找剩下的第 k 个if(l1m)returnnums2[l2k-1];// 边界情况 2nums2 里的数全被淘汰光了if(l2n)returnnums1[l1k-1];// 边界情况 3k 减到了 1说明下一个就是要找的数直接挑俩指针当前指着的最小值if(k1)returnmin(nums1[l1],nums2[l2]);// 各自往前看 k/2 个元素注意加上当前的偏移量 l1/l2并且千万别越界intidx1min(l1k/2-1,m-1);intidx2min(l2k/2-1,n-1);// 谁的“界碑”小就大胆淘汰谁及它前面的那截元素if(nums1[idx1]nums2[idx2]){// 精准扣减 k 值减去这次实际淘汰的元素个数k-(idx1-l11);// 把 nums1 的指针推到被淘汰元素的下一个位置l1idx11;}else{k-(idx2-l21);l2idx21;}}}public:doublefindMedianSortedArrays(vectorintnums1,vectorintnums2){intnnums1.size(),mnums2.size();inttotalLengthnm;// 奇偶情况拆分复用 getKth 逻辑if(totalLength%21){returngetKth(nums1,nums2,totalLength/21);}else{return(getKth(nums1,nums2,totalLength/2)getKth(nums1,nums2,totalLength/21))/2.0;}}};迭代版的核心变化就这三点循环代替递归用一个while (true)死循环罩住满足边界条件就直接return结果。指针推进之前是靠传递各种l1, r1缩小范围现在只需要维护l1和l2两个起始指针不断向右推相当于逻辑上把左边的元素给“截断”了。内存极简除了几个整型变量什么额外空间都没开辟。
性能陷阱与向量化替代方案全解析)
