`
zyn010101
  • 浏览: 324957 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

查找最小的K个数

阅读更多
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);
		}
		
	}

}

 

0
0
分享到:
评论

相关推荐

    Python实现查找最小的k个数示例【两种解法】

    本文实例讲述了Python实现查找最小的k个数。分享给大家供大家参考,具体如下: 题目描述 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 解法1 使用partition...

    最小的K个数1

    描述部分提供了一个具体的例子,说明了如何找出数组中的最小K个数。例如,对于数组`[4, 5, 1, 6, 2, 7, 3, 8]`,我们要找的是最小的4个数,即`[1, 2, 3, 4]`。在示例1中,输入数组为`[3, 2, 1]`,K值为2,输出可以是...

    查找和最小的K对数字(python)1

    为了找到最小和的 `k` 对数字,我们首先计算了两个数组的长度 `len_a` 和 `len_b`,并创建了一个空字典 `dic` 来存储每个数对的和以及其对应的数组索引。接着,我们遍历 `nums1` 和 `nums2`,计算每一对数字的和,并...

    查找最小的k个元素-java版

    输出一组元素中的最小的k个元素。例如数据集为:{1、8、3、6、5、4、7、2},则最小的4个数字为1,2,3和4。 【基本要求】 由随机数产生测试数据,测试数据不小于10000个,测试k的不同取值对算法的影响,如k=10、50、...

    js代码-最小k个数

    标题 "js代码-最小k个数" 暗示了我们正在探讨JavaScript中关于找到数组里最小k个数的问题。这是一个常见的算法问题,通常在数据结构和算法的学习中出现,对于编程面试和优化数据处理非常有帮助。我们将深入讨论如何...

    查找第k小2_K._查找第k小_

    在计算机科学和编程领域,"查找第k小"是一个常见的问题,它涉及到排序算法和数据结构的使用。这个问题的目标是在一个未排序或者部分排序的数组或列表中,快速找到第k小(或大)的元素。这个任务对于优化数据处理和...

    C语言TOP-K问题(从一堆数据中找出最大的k个数或者最小的k个数)

    在C语言中,处理大数据集并找出其中最大的k个数或最小的k个数是一个常见的问题,这通常涉及到数据结构中的“堆”概念。堆是一种特殊的树形数据结构,满足以下性质:每个父节点的值要么大于等于其子节点(大顶堆),...

    373. Find K Pairs with Smallest Sums查找和最小的k对数字【LeetCode单题讲解系列】

    373._Find_K_Pairs_with_Smallest_Sums查找和最小的k对数字【LeetCode单题讲解系列】

    python-leetcode面试题解之第373题查找和最小的K对数字.zip

    题目描述:你有两个整数数组nums1和nums2,你需要找出并返回这两个数组中和小于目标值target的最小K对数字。你可以假设每对数字只会出现一次。 解决此类问题时,常见的策略是使用双指针法。首先,可以将数组nums2...

    在一堆数中取得前K个最大最小的数的方法

    4. **二分查找**:设定一个范围[Smin, Smax],通过二分查找的方式确定第K个最大或最小的数。平均时间复杂度为O(n*logn)。 - **优点**:适用于各种规模的数据集。 - **缺点**:相对而言,实现较为复杂。 5. **...

    373.查找和最小的-k-对数字.cpp

    373.查找和最小的-k-对数字.cpp

    算法中最小K元素的选择问题

    在计算机科学中,"算法中最小K元素的选择问题"是一个重要的数据结构和算法主题,它涉及到从一个无序或有序的数组中找到第K小(或大)的元素。这个问题在各种应用场景中都有广泛的应用,比如数据库查询优化、排序算法...

    基于二分查找的有序表在做topK算法的给力实现

    关键在于如何在不改变原始数组顺序的情况下,找到第K大的元素,并保持前K个元素的相对大小关系。 5. **优化技巧**:在实现中,可能会用到最小堆或优先队列等数据结构,它们可以在O(log K)的时间复杂度内完成插入和...

    几种查找数组的前K个最小值的算法.docx

    该方法首先给定一个K个大小的数组b,然后复制数组a中的前K个数到数组b中,将这K个数当成数组a的前K个最小值,对数组b创建最大堆,然后遍历数组a,比较数组a中的其他元素,如果其他元素小于数组b的最大值(堆顶),则...

    1_example.zip 第k个最小整数

    为了分析和验证这些算法,你可以参考"排序查找最小的第k个数.docx"文档,它可能包含了具体的代码示例和进一步的解释。同时,"example"可能是实现这些算法的一个测试用例或者数据集,用于检查算法的正确性。 总之,...

    第k小元素查找C++程序实现

    这个问题的基本目标是从一个未排序或已排序的数组或集合中找出第k个最小的元素。这里我们将深入探讨三种方法来解决这个问题:中位选择法、随机选择查找以及排序查找。 1. **中位选择法**: 中位选择法是一种高效...

    分治算法求最大值与最小值,找最小元素

    在本题中,我们关注的是如何运用分治算法来找到一组数字中的最大值和最小值,以及如何找出第k个最小元素。这两个问题都可以通过分治思想进行有效解决。 首先,寻找最大值和最小值。传统的做法是遍历整个数组,但...

    求一个数组最小的两个数的下标

    这种方法的时间复杂度可以达到O(n log k),其中k是堆的大小,对于找到前k个最小元素非常有效。 VC6.0是Visual C++ 6.0的简称,是微软发布的一个集成开发环境,用于编写C++代码。虽然现在版本较旧,但仍然可用于教学...

    海量数据查找数据问题

    接下来,我们讨论在海量数据中查找一个特定的数。这个问题可以通过构建索引来解决。B树、B+树和哈希表都是常见的索引结构。B树和B+树适合磁盘存储,它们的分支因子较大,可以减少磁盘I/O操作。B+树所有数据都存储在...

Global site tag (gtag.js) - Google Analytics