设计一组N个数,确定其中第k个最大值,方法很多,最直观的想法是将n个数由大到小排好序,取第k个数即可,但效率并不高。
网上的方法如下:
解法1: 我们可以对这个乱序数组按照从大到小先行排序,然后取出前k大,总的时间复杂度为O(n*logn + k)。
解法2: 利用选择排序或交互排序,K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)
解法3: 利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。这时有两种情况:
1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数;
2. Sa中元素的个数大于等于k,则返回Sa中的第k大数。时间复杂度近似为O(n)
解法4: 二分[Smin,Smax]查找结果X,统计X在数组中出现,且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)
解法5:用O(4*n)的方法对原数组建最大堆,然后pop出k次即可。时间复杂度为O(4*n + k*logn)
解法6:维护一个k大小的最小堆,对于数组中的每一个元素判断与堆顶的大小,若堆顶较大,则不管,否则,弹出堆顶,将当前值插入到堆中。时间复杂度O(n * logk)
解法7:利用hash保存数组中元素Si出现的次数,利用计数排序的思想,线性从大到小扫描过程中,前面有k-1个数则为第k大数,平均情况下时间复杂度O(n)
解法3:是比较好一种,用快排来做,java实现代码如下:
package algorithm; /** * @author fengzb.fnst * */ public class N_element { private static int partition(int[] L, int low, int high) { int temp = L[low]; int pt = L[low]; // 哨兵 while (low != high) { while (low < high && L[high] <= pt) high--; L[low] = L[high]; while (low < high && L[low] >= pt) low++; L[high] = L[low]; } L[low] = temp; return low; } public static void quickSort(int[] L, int low, int high) // 快速排序 { int pl; if (low < high) { pl = partition(L, low, high); quickSort(L, low, pl - 1); quickSort(L, pl + 1, high); } } public static void findk(int k, int[] L, int low, int high) { int temp; temp = partition(L, low, high); if (temp == k - 1) { System.out.println("第" + (temp + 1) + "大的数是:" + L[temp]); } else if (temp > k - 1) findk(k, L, low, temp - 1); else findk(k, L, temp + 1, high); } public static void main(String[] args) { int[] a = { 15, 25, 9, 48, 36, 100, 58, 99, 126, 5 }; int i, k; System.out.println("排序前:"); for (i = 0; i < 10; i++) { System.out.print(a[i] + " "); } System.out.println(); k = 4; N_element.findk(k, a, 0, 9); N_element.quickSort(a, 0, 9); System.out.println("排序后:"); for (i = 0; i < 10; i++) { System.out.print(a[i] + " "); } } }
执行结果
排序前: 15 25 9 48 36 100 58 99 126 5 第4大的数是:58 排序后: 126 100 99 58 48 36 25 15 9 5
相关推荐
对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1...
2、输入n和k(n》=k)求n个数字的(n,k)排列 如n=3,k=2 输入的三个数位1 2 3 则输出 12 13 21 23 31 32 3、输入n个数(有重复),求n个数字的全排列 如:n=3 全排列的数字为1 1 2 则输出 112 121 211 4、输入...
在N个数字中,删除K个,使剩余的数字最小。
这是一个用C++写的简单算法,里面没用到什么高深的东西,就是基本的控制语句组成。
分析:求解k个数的不同组合,我们可以用一维数组a[0]~a[k-1]来保存其中的一个结果,因为组合...所以a[k-1]即组合中的最后一个数,只能为k~n 令i=a[k-1] 则 i>=k && i<=n 完整代码请参考我的博客文章,这里只是核心部分
利用分治法,解决对N个字中求第K大的数字的问题,效率比起逐个扫描有素提高
问题描述: 给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列成一个新的正整数。 算法设计: 给定n (1<=n)位的正整数a和k...试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。
编程求解:输入两个整数 n 和 m,从数列 1,2,3.......n 中随意取几个数,使其和等于m ,要求将其中所有的可能组合列出来。
给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列成一个新的正整数。 算法设计: 给定n (1<=n)位的正整数a和k,此时,k小于n。 试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数...
题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。 程序源代码: main() { ...
输入N个数,从N个数中任意选择1个或多个数,使得其和是N的倍数( N )
统计数字问题 一本书的页码从自然数1 开始顺序...程序运行结束时,输出有10行,在第k行输出页码中用到数字k-1 的次数,k=1,2,…,10。 Sample Input 11 Sample Output 1;4;1;1;1;1;1;1;1;1(竖着的!)
最近Catcher对数字游戏很感兴趣,他发明了一种新的游戏,给出一个数N.问N是否能表示成某个正整数X的K次幂(K>1),N可能有多种表示方法,请找出最大的X并输出相应的K.例如 16=2^4=4^2,64=4^3=2^6=8^2则16应表示...
输入一个N位高精度的正整数,去掉其中任意K个数字后剩下的数字按原左右次序组成一个新的正整数。写算法对给定的N和K,寻找一种方案使得剩下的数字组成的新数最小。 输入:N、K以及一个N位高精度的正整数 输出:剩下...
对于一个有 n 个数字的正整数 a, 去掉其中任意 k (≤ n) 个数字后, 剩下的数字按原次序排列组成一个新的正整数. 本题对于给定的正整数 a, 请计算删去 k 个数字后得到的最小数. Input 有多个测试用例. 每个测试...
问题描述: 给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列成一个新的正整数。 算法设计: 给定n (1<=n)位的正整数a和k...试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。
问题描述: 给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列成一个新的正整数。 算法设计: 给定n (1<=n)位的正整数a和k...试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。
本代码文档利用回溯法思想,实现了n位正整数去掉k位数字得到最小数,并且含有测试代码,非常简单,详细,准确!