本文共 1588 字，大约阅读时间需要 5 分钟。

题目描述：输入n个整数，找出其中最小的K个数例如输入4，5，6，1，2，3，7，8这8个数字则最小的4个数字是1，2，3，4

方法一：对数组进行排序 时间复杂度O（nlogn)

import java.util.ArrayList;import java.util.Arrays;public class GetLeastNumbers {
       public static ArrayList
   
     getLeastNumbers(int[] input,int k){
           ArrayList
    
      list=new ArrayList
     
      ();        if(input.length==0 ||input==null||k>input.length){
               return  list;        }        Arrays.sort(input);        if(k==1){
               System.out.println(input[0]);        }        for(int i=0;i
     
    
   

其中Arrays.sort()也可以换为各种排序方法：例如下面的冒泡排序法：

for(int i=0;i
   
     input[j]) {
                       int temp = input[i];                    input[i] = input[j];                    input[j] = temp;                }            }        }
   

方法二：将数组分成前k个数和后n-k个数，定义一个指针再后部分移动，找出前面部分数中最大数的下标，如果指针指向的数比前k个数的最大值小时，就将这个最大值替换为指针指向的数

public class GetLeastNumbers {
       public static ArrayList
   
     getLeastNumbers(int[] input,int k) {
         ArrayList
    
      list = new ArrayList
     
      ();        if (input.length == 0||input==null||k>input.length){
               return list;        }        for(int i=0;i
      
        list){
           int index=0;        int a=list.get(0);        for(int i=1;i
       
        a){
                   a=list.get(i);                index=i;            }        }        return index;    }    public static void main(String[] args) {
           int[] a={
   4,5,6,1,2,3,7,8};        int k=4;        ArrayList
        
          list=new GetLeastNumbers().getLeastNumbers(a,k); for(int i:list){ System.out.print(i+" "); } }}
        
       
      
     
    
   

转载地址：http://tylzi.baihongyu.com/