题设:
/**
* Created by Lanxiaowei
* Craated on 2016/12/13 9:46
* 从一个无序的数字序列中查找出前K个最大的数字,
* 要求返回的K个数字在目标无序数组中是前K个最大的,但是不要求这前K个数字是有序的
* 比如:8 9 5 0 6 2 7 1 4 3 且K = 5,那么最终应该返回
* 9 8 7 6 5 或者 6 5 8 7 9
*/
public class TopKProblems { public static void main(String[] args) { int k = 5; int[] array = {8, 9, 5, 0, 6, 2, 7, 1, 4, 3}; List<Integer> result = new ArrayList<Integer>(); findTopKBig(array,0,array.length, k,result); if(null == result || result.size() <= 0) { System.out.println("No results."); return; } for(int i=0; i < result.size(); i++) { System.out.print(result.get(i) + " "); } } /** * 从从一个无序的数字序列中查找出前K个最大的数字 * @param array 待查找的无序数组 * @param offset 查找的起始偏移量 * @param n 待查找的前N个 * @param k 表示最终需要返回的前K个 * @return */ public static List<Integer> findTopKBig(int[] array,int offset,int n,int k,List<Integer> result) { if(n <= 0) { return null; } if(result == null) { result = new ArrayList<Integer>(); } //如果k >= n,则直接返回整个数组即可 if(k >= n) { for(int i=offset; i < offset + n; i++) { result.add(array[i]); } return result; } //a1表示中间那个元素,a1将整个数组分成左大右小两部分 int a1 = array[offset]; //头指针 int y = offset; //尾指针 int z = offset + n - 1; int n1 = 0; int n2 =0; while (y < z) { //从头指针往尾指针遍历 while (array[z] <= a1 && y < z) { z--; } if(y < z) { array[y] = array[z]; } //从尾指针往头指针遍历 while (array[y] > a1 && y < z) { y++; } if(y < z) { array[z] = array[y]; } } //此时头尾指针重合,找到a1的位置即中间的那个元素 array[y] = a1; //计算a1前面的元素总个数即左边比较大的元素总个数 n1 = y - offset + 1; //计算a1后面的元素总个数即右边比较小的元素总个数 n2 = n - n1; //如果k >= n1,那么直接返回前n1个元素 if(n1 <= k) { for(int i=offset; i <= y; i++) { result.add(array[i]); } } //如果k < n1,那么就需要在[offset,n1 - 1]范围内查找前K个最大的数字 if(n1 > k) { return findTopKBig(array,offset,n1 - 1 ,k,result); } //如果k > n1,那么就需要在[y + 1,n2]范围内查找前K个最大的数字,这里的y+1其实表示的就是a1后面的那个元素即 //从a1后面的n2个比较小元素里查找剩下的符合要求的数字 if(n1 < k) { return findTopKBig(array,y + 1,n2,k - n1,result); } return result; } }
相关推荐
代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间...
折半查找的递归算法,非常实用,可以实现的C语言程序
编写递归算法,在二叉树中求位于先序序列中第K个位置的结点。
C# 用递归的方式查找指定文件夹下的所有子目录,C#代码 采用递归的方法來查找指定文件夹及它的所有子文件夹裏的内容。
迭代顺序查找、递归顺序查找、二分查找之间的对比
C语言递归查找最大值程序 C语言初学者必会
非递归查找的简单C语言程序,供初学者参考一下,哈哈。
用C语言开发的递归和非递归二分查找算法,具体内容详见代码
分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。
否则,重新对当前排列从后向前扫描,找到第一个大于i的元素k,交换i和k,然后对从j开始到结束的子序列反转,则此时得到的新排列就为下一个字典序排列。这种方式实现得到的所有排列是按字典序有序的,这也是C++ STL...
无限级树正向查找、反向查找例子【递归实现】 无限级树正向查找、反向查找例子【递归实现】 无限级树正向查找、反向查找例子【递归实现】
这是一个java文件用于递归查找一个目录下的所有文件夹中的文件是否含有特殊字符串
Java二分查找递归算法
递归折半查找法基本的程序思想,初学者可以参考一下。
递归图(reecurrence plots),从相空间重构时间序列的matlab程序,
foreach字符串递归查找.rar
数据结构第二章上机作业,张宪超。 已知head为单链表的表头指针,链表中储存的都是整形数据,实现下列运算的递归算法: 1.求链表中最大值 2.求链表中的节点个数 3.求所有整数平均值
初等数论中最大公约数、最小公倍数(递归实现)程序初等数论中最大公约数、最小公倍数(递归实现)程序初等数论中最大公约数、最小公倍数(递归实现)程序
//二分查找,递归实现 int binarySearch(int a[],int low,int high,int key) { //查找某元素是否在数组中,若存在,则返回下标,否则返回-1; int mid=(low+high)/2; if(low>high){ return -1;//该元素不...