问题:《编程之美》page139.寻找最大的k个数。
方法一:通过全排序(快速排序),然后获取前k个数即位最大的k个数。算法复杂度:O(nlogn).
方法二:通过部分排序。(选择排序,冒泡排序),直接获取前k个最大的数。算法复杂度O(n*k).当k比较小的时候可以考虑
方法三:快速排序的变种。前面寻找数组中第k大数的过程中,当找准数组中第k大数的位置时,数组中比k大的数据都在k的left边,比k小的数据都在k的right边。从而获取前k大的数据。其实也是部分排序。算法复杂度:O(n).
public class FindKth {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array=new int[]{2,4,3,4,7};
int k=4;
find(array,0,array.length-1,k-1);
}
public static void find(int[] array,int left, int right,int k){
if(k==left && k==right) {
System.out.println("the "+(k+1)+"th max number is:" + array[k]);
print(array,k);
return ;
}
int i=left;
int j=right+1;
int key=array[left];
while(true){
do{
i++;
}while(i<=right&&array[i]>key);
do{
j--;
}while(j>=left&&array[j]<key);
if(j<i) break;
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
int tmp=array[left];
array[left]=array[j];
array[j]=tmp;
if(j==k) {
System.out.println("the "+(k+1)+"th max number is:" + array[j]);
print(array,k);
return ;
}
if(k<j)
find(array,left,j-1,k);
else
find(array,j+1,right,k);
}
public static void print(int[] array,int k){
System.out.println("find numbers are: ");
for(int i=0;i<=k;i++){
System.out.print(array[i]+ " ");
}
}
}
运行结果:
the 4th max number is:3
find numbers are:
7 4 4 3
方法四:如果N很大,比如100亿。可以采用一个数组,数组中始终保持访问过的所有的数中的前k个最大的数据,每次从k个数中淘汰掉最小的数,到最后可以一次遍历获取前k个最大的数据。通过维持一个容量为k的最小堆的方式来实现。算法复杂度O(n*log2k)
分享到:
相关推荐
给定一数组,查找数组中第k大的数。代码中借助快速排序中的partition方法来实现。
典型的Top K算法 找出一个数组里面前K个最大数.doc
在编程中非常常用的算法:计算整形数组中第k小的数
主要介绍了Python实现查找数组中任意第k大的数字算法,涉及Python针对数组的排序、查找等相关操作技巧,需要的朋友可以参考下
求有N个元素的数组中前k个最大的数?(N>=k) 方法一:排序法 可以先将数组排序,然后再截取前k个最大的数,利用归并排序或者快速排序等排序方式,该方法平均时间复杂度为O(N*logN) 方法二:部分排序法 由于只需要找出...
c语言面试题 c语言面试题之双指针数组中的K-diff数对
17082 两个有序数序列中找第k小(必做) 时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0 题型: 编程题 语言: C++;C;VC;JAVA Description 已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为...
本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法。分享给大家供大家参考,具体如下: 从一个无序的整型数组中选出第k小的数,如k=1为最小数,k=n为最大数。这里数组可以是有重复的值! 下面是自己写的...
在主函数中输入10个整数到数组中,调用函数move()完成将数组元素循环移动k位(要求函数参数为:1数组名;2数组元素个数;3循环移动的位数k)。当k>0时,实现循环右移;当k时,实现循环左移。循环右移一位的意义是:将...
示例2:输入:[1, 2, 3, 4, 5], k = 1输出: 4解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和
js代码-数组中的第K个最大元素
J, K两种类型热电偶的分度表数组,浮点型数组。H头文件。方便用于工程计算和相关编程应用。每一度一个浮点数,K型热电偶的数组范围从-60度到+1370度;J型热电偶的温度范围:-210度到+1200度。
已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为n, 现在请你用分治算法,找出X和Y的第k小的数,算法时间复杂度为O(max{logm, logn})。
该问题还可以变形为:有一个大小为 n的数组A[0,1,2,…,n-1],求其中前k大的数。一字之差,原问题是“第k大”,变形的问题是“前k大”,但是平均时间复杂度却都可以控制在O(n),这不由得让人暗暗称奇。我们先分析原...
易语言随机打乱数组源码,随机打乱数组
数与数组加减:k+/-A %k加或减A的每个元素 数组乘数组: A.*B %对应元素相乘 数组乘方: A.^k %A的每个元素k次方;k.^A,分别以k为底A的各元素为指数求幂值 数除以数组: k./A和A./k %k分别被A的元素除 数组除法: ...
算法设计与分析(王晓东版)2-11题:将数组的子数组a[0:k]和a[k+1:n-1]进行换位,要求最坏情况下时间复杂度为O(n)
求数组中第K大的数可以基于快排序思想,步骤如下:1、随机选择一个支点2、将比支点大的数,放到数组左边;将比支点小的数放到数组右边;将支点放到中间(属于左部分)3、设左部分的长度为L,当K < L> L时,递归地在有...
首先将向量V从中间位置分开,分成左和右,分好后,中间值的索引如果恰恰等于K,就找到了,否则如果中间元素索引大于K,则在左子表中继续查找,忽略右子表,如果中间值索引小于K,则在右子表中继续查找,如此循环往复...