最小k个数-剑指offer-Java

古城微笑少年丶 2021-12-13 04:44 226阅读 0赞

## 题目描述 ##

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

解题思路：采用堆排序

1）将前k个元素构造最大堆，i=0~k-1；

2）从第k个开始，依次与最大堆得堆顶元素进行比较，如果比堆顶元素小，则进行交换，维护最大堆。

3）最后堆内为最小k个数。

每次比较与堆根进行比较，当一个数比堆根大得时候，那就是比堆中所有得数都大，如果比堆根小，那就替换堆根。

> 1.  import java.util.\*;
> 2.  public class Solution \{
> 3.      public ArrayList<Integer> GetLeastNumbers\_Solution(int \[\] input, int k) \{
> 4.          ArrayList<Integer> list = new ArrayList<Integer>();
> 5.           if(input.length==0 || k<=0 || k>input.length) return list;
> 6.          for(int i=k/2-1;i>=0;i--)
> 7.          \{
> 8.              buildMaxHeadpSort(input,i,k);
> 9.          \}
> 10.         for(int j=k;j<input.length;j++)
> 11.         \{
> 12.             if(input\[j\]<input\[0\])
> 13.             \{
> 14.                 swap(input,j,0);
> 15.                 buildMaxHeadpSort(input,0,k);
> 16.             \}
> 17.         \}
> 18.         for(int i=k-1;i>=0;i--)
> 19.         \{
> 20.             list.add(input\[i\]);
> 21.         \}
> 22.              return list;
> 23.         \}
> 24.      public void buildMaxHeadpSort(int input\[\],int i, int k)
> 25.      \{
> 26.          int leftc = 2\*i;
> 27.          int rightc = 2\*i+1;
> 28.          int larg = i;
> 29.          if(leftc < k && input\[i\]<input\[leftc\])
> 30.          \{
> 31.              larg = leftc;
> 32.          \}
> 33.          if(rightc < k && input\[larg\] < input\[rightc\])
> 34.          \{
> 35.              larg = rightc;
> 36.          \}
> 37.          if(larg != i)\{
> 38.              swap(input,i,larg);
> 39.              buildMaxHeadpSort(input,larg,k);
> 40.          \}
> 41.      \}
> 42.      public void swap(int input\[\],int i, int larg)
> 43.      \{
> 44.          int temp = input\[i\];
> 45.          input\[i\] = input\[larg\];
> 46.          input\[larg\] = temp;
> 47.      \}
> 48.     public void main(String\[\] args) \{
> 49.         int input\[\] = \{4,5,1,6,2,7,3,8\};
> 50.         int k = 4;
> 51.         ArrayList<Integer> list = GetLeastNumbers\_Solution(input,k);
> 52.         for(int i=0;i<list.size();i++)
> 53.             System.out.print(list.get(i)+" ");
> 54.     \}
> 55. \}

**扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20211210/39e80f3144394dac83180e2709551e28.png