package com.chinahrt.zyn.pango; import java.util.ArrayList; import java.util.List; public class FindMinKFromN { /** * 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 输入: 每个测试案例包括2行: 第一行为2个整数n,k(1<=n,k<=200000),表示数组的长度。 第二行包含n个整数,表示这n个数,数组中的数的范围是[0,1000 000 000]。 输出: 对应每个测试案例,输出最小的k个数,并按从小到大顺序打印。 样例输入: 8 4 4 5 1 6 2 7 3 8 样例输出: 1 2 3 4 */ public List<Integer> getMinList(Integer[] num,int k){ List<Integer> list = new ArrayList<Integer> (); for(Integer i:num){ list = addInteger(list,i,0,list.size()==0?0:list.size()-1,k); } return list; } public List<Integer> addInteger(List<Integer> list ,int a,int startIndex,int endIndex,int length){ if(list.size()==0){ list.add(a); return list; } //如果小于最小的插入前面 if(a<=list.get(startIndex)){ list.add(startIndex,a); if(list.size()>length){ list.remove(list.size()-1); } return list; } //如果大于最大的插入后面 if(a >= list.get(endIndex)){ list.add((endIndex+1),a); if(list.size()>length){ list.remove(list.size()-1); } return list; } //如果位于两者之间,插入 if(list.get(startIndex)<a &&((endIndex -startIndex)==1) && list.get(endIndex)>a){ list.add((startIndex+1),a); if(list.size()>length){ list.remove(list.size()-1); } return list; } //如果以上都不执行,二分查找比较插入 int middle; if((endIndex - startIndex)%2!=0){ middle = (endIndex - startIndex+1)/2; }else{ middle = (endIndex - startIndex)/2; } if(a>list.get(middle)){ return addInteger(list,a,middle,endIndex,length); }else{ return addInteger(list,a,startIndex,middle,length); } } /** * @param args * Administrator * 2013-4-13 上午10:26:50 */ public static void main(String[] args) { // TODO Auto-generated method stub FindMinKFromN f = new FindMinKFromN(); Integer[] a = {4,5,1,6,2,7,3,8}; List<Integer> list = f.getMinList(a, 4); for(Integer b:list){ System.out.println(b); } } }
相关推荐
本文实例讲述了Python实现查找最小的k个数。分享给大家供大家参考,具体如下: 题目描述 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 解法1 使用partition...
输出一组元素中的最小的k个元素。例如数据集为:{1、8、3、6、5、4、7、2},则最小的4个数字为1,2,3和4。 【基本要求】 由随机数产生测试数据,测试数据不小于10000个,测试k的不同取值对算法的影响,如k=10、50、...
373._Find_K_Pairs_with_Smallest_Sums查找和最小的k对数字【LeetCode单题讲解系列】
373.查找和最小的-k-对数字.cpp
示例 1:输出: [1,2],[1,4],[1,6]解释: 返回序列中的前 3 对数:示例 2:输出: [1,1],[1,1]解释: 返回序列中的前 2 对数:
可以运行的查找第K小元素的实现代码。并且实现了多个元素相同的算法。与王晓东的《算法》配套
1. 设计程序利用分治策略求n个数的最大值和最小值。 2. 利用分治策略,在n个不同元素中找出第k个最小元素。
MINMAX 查找第 k 个最小值或最大值及其索引。 用法: vals = minmax(data) % 找到最小值vals = minmax(data,k) % 找到第 k 个最小值vals = minmax(data,k,flag) % 找到第 k 个最大值[vals,loci] = minmax(:) [vals,...
所以我们需要找出数组中最大的三个数的乘积m,然后与数组中最小的两个数相乘再与最大的数相乘的结果n,然后比较m,n,选出最大的数即为最终的结果。 参考代码://www.jb51.net/article/121189.htm 实现代码: #...
//e为存储线性表的数组,n为线性表的结点个数 { int i,j,k,t; for(i=0;i;i++) //控制n-1趟的选择步骤 //e[i],e[i+1],…,e[n-1]中选择键值最小的结点e[k] { for(k=i,j=i+1;j;j++) if(e[k]>e[j]) k=j;...
在编程中非常常用的算法:计算整形数组中第k小的数
因为在Java库函数里,... //定义一个静态内部类,继承Comparator接口,并重写他的compare方法 //return o2-o1 就可以 @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } } pu
根据现有的基于信号强度的室内无线定位算法,结合二分查找的思想,提出了一种具有较低复杂度的室内无线定位算法,即快速最小K邻居定位算法。该算法通过将定位区域划分为多个子区域,利用优化的计算迅速缩小定位区域...
给定一个数组 A[1...N],它找到两个给定索引之间具有最小值的元素的位置。 它在恒定时间内返回答案。 RMQ 问题可用于在恒定时间内恢复图中的 lca(最低共同祖先)。 有关更多详细信息,请参阅...
利用随机函数产生50个0-20之间的随机整数,存放在序列中,再通过键盘输入一个整数KEY,查找50个随机整数中是否有KEY值,如果存在,则输出他们所有的位置 题5. 回文数判断:设N是一任意自然数,如果N的各位数字反向...
计算循环队列的元素个数:“尾指针减头指针”,若为负数,再加其容量即可。 1.5 链表 在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。其中...
两个有序数组的中位数 k 最近元素 力量 丑陋的数字 获取 H 指数 查找重复号码 找到超过 25% Kth相关问题 4和 最短距离 范围 最长公共前缀 二和 游泳 最小的矩形 最小数的计数 调度 最大总和 最小的好基 娃娃 范围...
Java面试 Java超级经典100问题 Java高级开发工程师必备 Java面试宝典 1.赋值运算函数.2.单例设计模式.3....找出最小的K个数31.连续子数组的最大和.32.从1到整数n中1出现的次数.33.把数组中的数排成一个最小的数.3
30. 找出最小的K个数 31. 连续子数组的最大和 32. 从1到整数n中1出现的次数 33. 把数组中的数排成一个最小的数 34. 求第N个丑数 35. 第一个出现一次的字符 36. 数组中逆序对的个数 37. 两个链表的第一个公共...