问题:有一个大小为n的数组A[0,1,2,…,n-1],求其中第k大的数。
该问题是一个经典的问题,在《算法导论》中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们的意料,此处暂且不表。
该问题还可以变形为:有一个大小为 n的数组A[0,1,2,…,n-1],求其中前k大的数。
一字之差,原问题是“第k大”,变形的问题是“前k大”,但是平均时间复杂度却都可以控制在O(n),这不由得让人暗暗称奇。
我们先分析原问题:有一个大小为 n的数组A[0,1,2,…,n-1],求其中第k大的数。
我们先取特例,令k=1,那么就是取最大的数,只要扫描一遍数组就可以确定该值,如果k=2,则扫描两边数组就可以确定第二大的数,依此类推下去,时间复杂度是O(k*n),如果k跟n是一个数量级,那么时间复杂度就是O(n*n)了,显然不是最优的解法。
考虑分治法,难点在于如何将该问题分解为两个子问题。
快速排序最基础的一步:
随机取某一个数x,将其与数组末尾元素交换,然后将比其小的数交换至前,比其大的数交换至后。
这一步使某一数组的快速排序问题分解成两个子数组的排序问题,现在我们就依此来解决取第k大的数这个问题。
设数组下表从0开始,至n-1结束。
1、 随机取某个数,将其与数组末尾元素交换。
a) idx=rand(0,n-1);生成[0,n-1]间的随机数。
b) Swap(array[idx], array[n-1]);
2、 用末尾元素x,将比x小的数交换至前,比x大的数交换至后,并返回此时x在数组中的位置mid。
3、 如果mid==n-k,那么返回该值,这就是第k大的数。
如果mid>n-k,那么第k大的数在左半数组,且在左半数组中是第k-(n-mid)大的数。
如果mid<n-k,那么第k大的数在右半数组,而且仍然是第k的数。
方法一:
方法二:
-
#include"iostream"
-
usingnamespacestd;
-
-
intrandom_partion(int*p,intn)
-
{
-
intidx=rand()%n;
-
swap(p[idx],p[n-1]);
-
inti=-1;
-
intj=0;
-
for(j=0;j<n;j++)
-
{
-
-
if(p[j]<p[n-1])
-
{
-
swap(p[++i],p[j]);
-
}
-
}
-
swap(p[++i],p[n-1]);
-
returni;
-
}
-
-
intgetMaxK(int*p,intn,intk)
-
{
-
intmid;
-
if(k<=0)
-
return-1;
-
if(n<k)
-
return-1;
-
mid=random_partion(p,n);
-
if(mid==n-k)
-
returnp[mid];
-
elseif(mid<n-k)
-
returngetMaxK(p+mid+1,n-mid-1,k);
-
else
-
returngetMaxK(p,mid,k-(n-mid));
-
}
-
-
intmain(void)
-
{
-
intnum,a[]={12012,3,945,965,66,232,65,7,8,898,56,878,170,13,5};
-
num=getMaxK(a,15,4);
-
printf("%d\n",num);
-
system("pause");
-
return0;
-
}
分享到:
相关推荐
当K < L> L时,递归地在有部分中找第(K – L)大的数当K = L时,返回左右两部分的分割点(即原来的支点),就是要求的第K大的数以上思想的代码实现如下: 代码如下:/**线性时间复杂度求数组中第K大数** author :...
本篇文章是对数组中求第K大数的实现方法进行了详细的分析介绍,需要的朋友参考下
典型的Top K算法 找出一个数组里面前K个最大数.doc
求有N个元素的数组中前k个最大的数?(N>=k) 方法一:排序法 可以先将数组排序,然后再截取前k个最大的数,利用归并排序或者快速排序等排序方式,该方法平均时间复杂度为O(N*logN) 方法二:部分排序法 由于只需要找出...
本文实例讲述了C++实现的O(n)复杂度内查找第K大数算法。分享给大家供大家参考,具体如下: 题目:是在一组数组(数组元素为整数,可正可负可为0)中查找乘积最大的三个数,最后输出最大乘积。 从题目我们知道只有两...
20位左右的大数相乘算法解析,用一个整型数组表示一个大数,数组的每个元素储存大数的一位数字,则实际的大数d表示为: d=a[k]*10的k-1次幂+a[k-1]*10的k-2次幂+......+a[2]*10+a[1] 其中a[0]保存该大数的位数. ...
解法1: 我们可以对这个乱序数组按照从大到小先行排序,然后取出...2. Sa中元素的个数大于等于k,则返回Sa中的第k大数。时间复杂度近似为O(n) 解法4: 二分[Smin,Smax]查找结果X,统计X在数组中出现,且整个数组中比X大
c++编程 分治方法实现获取数组第k大数 使用类似快速排序,执行一次快速排序后,每次只选择一部分继续执行快速排序,直到找到第K个大元素为止。
二分法、回溯法、剪枝DFS、BFS、动态规划、位运算、数学、大数、排列有限状态自动机、排序、归并排序、归并思想、滚动数组优化、双指针、分治法二叉树遍历、问题抽象、递归、俄罗斯农民乘法、滑动窗口、约瑟夫环、双...
查找数组的“第 K 个”最大和最小元素 Array 给定一个只包含 0、1 和 2 的数组。不使用任何排序算法对数组进行排序 Array 将所有负元素移动到数组的一侧 Array 找出两个已排序数组的并集和交集。 数组 编写一个程序...
求大数的阶乘 找到最大乘积子数组 找到最长的连续子序列 给定一个大小为 n 的数组和一个数字 k,找出出现次数超过“n/k”次的所有元素。 最多两次买卖股票的最大利润 判断一个数组是否是另一个数组的子集 找
1.1 从有序数组中删除重复元素 1.2 在排序数组被旋转后进行查找 1.3 寻找两个排序数组的中位数 1.4 最长连续序列 1.5 累加和 1.6 移除数组中指定值 1.7 下一个排列 1.8 第n个全排列 1.9 验证数独的正确性 1.10 容纳...
5.主席树(静态求区间第k小) (区间中小于k的数量和小于k的总和) (区间中第一个大于或等于k的值) 6.权值线段树 (求逆序对) 7.动态主席树 (主席树+树状数组) (区间第k大带修改) 8.树上启发式合并 (查询子树的优化) 9,...
| 第 K 短路(DIJKSTRA) 5 | 第 K 短路(A*) 5 | PRIM 求 MST 6 | 次小生成树 O(V^2) 6 | 最小生成森林问题(K 颗树)O(MLOGM). 6 | 有向图最小树形图 6 | MINIMAL STEINER TREE 6 | TARJAN 强连通分量 7 | ...
leetcode 530 算法和数据结构的基础课程 使用 Kadene 算法的最大子阵列问题 ...在旋转排序数组中查找元素 BST 是否对称(左右半边是镜像) 从 PRE-ORDER 构建 BST 给定数字范围的按位与 两个排序数组的中位数 最大平方
1.24 我在一个文件中定义了一个extern数组,然后在另一个文件中使用,为什么sizeof取不到数组的大小? 声明问题 1.25 函数只定义了一次,调用了一次,但编译器提示非法重声明了。 1.26 main的正确定义是什么?void ...
3N加1问题,绝对值,加法,无算术加法,约数和,分配数,弧长,面积,曲线下...卡德恩算法,Karatsuba算法,克里希纳穆蒂数,第K个字典序排列,非常大数的最大值,最大子数组和,最小公倍数,线段长度,Liouville函数等
数组中重复的数组 set/hashmap/原地交换顺序 jz17 打印从1到最大的n位数 注意大数解法 jz61 扑克牌中的顺子 直接用最大最小值比较最简单/逐个相减 jz58-2 字符串拼接 substring不能用的话用stringbuilder,还可以有...