校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 算法 > 高级排序(快排、堆排等)
题目

输入n个数,找出其中最小的k个数,例如输入4,5,1,6,2,7,3,8,个数字,则最小的数字是1,2,3,4。

解答

【解析】

基于O(n)的算法,可以用基于Partion函数解决这个问题,如果基于数组的第k个数字来调整,使得比第k个数字小的所有数字都位于数组的左边,比第k个数组大的所有数字都位于数组的右边,这样调整之后数组左边的k个数字就是最小的k个数字,不一定有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.Scanner;
  
  
public class Main {
  
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();
        int[] num=new int[n];
        int[] out=new int[k];
        for(int i=0;i<n;i++){
            num[i]=in.nextInt();
        }
       boolean b=GetMinK(n,num,k,out);
       if(b){
           for(int i=0;i<k;i++){
               System.out.print(out[i]+" ");
           }
       }
  
    }
    public static boolean GetMinK(int uiInputNum, int[] pInputArray, int uiK, int[] pOutputArray){
          if(pInputArray==null||pOutputArray==null||uiK>uiInputNum||uiInputNum<=0||uiK<=0){
             return false;
          }
          int start=0;
          int end=uiInputNum-1;
          int index=partition(pInputArray,start,end);
          while(index!=uiK-1){
                if(index>uiK-1){//index在k-1的右边
                     end=index-1;
                     index=partition(pInputArray,start,end);
                }
                else{
                    start=index+1;
                    index=partition(pInputArray,start,end);
                }
          }
          for(int i=0;i<uiK;i++){
              pOutputArray[i]=pInputArray[i];
          }
          return true;
           
    }
    //partion分区函数,返回数组a的首元素快排的索引值index
    public static int partition(int[] a,int start,int end){
          int privot=a[start];
          int i=start;
          int j=end;
          while(i<j){
              while(i<j&&privot<=a[j]){
                  j--;
              }
              swap(a,i,j);
              while(i<j&&privot>=a[i]){
                  i++;
              }
              swap(a,i,j);
          }
          return i;
           
    }
    public static void swap(int[] a,int i,int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}


C 0条回复 评论

帖子还没人回复快来抢沙发