剑指Offer 30 *最小的k个数

题目描述

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

思路

  1. 第一反应肯定是排序呗；冒泡啊，快排啊，反正排好序就行了，下面我写了一个用Treeset的，直接全扔进去，就是有序的了；时间复杂度？那肯定就不是我控制得了；
  2. 快排，思路很简单，就是找寻哨兵呗；不过原来的数组会被改变；
  3. 小根堆解法，每次跟都是最小值；调整几次，就得到几个最小值，就是这样；

    代码

    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
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    public class Ten {
        public  static  void  main(String [] arg)
        {
                int [] n=null;
                int [] n1 ={4,5,1,6,2,7,3,8};
                int [] n2 = {8,5,3,2,1,5};
            ArrayList arrayList =new ArrayList();
           arrayList= (GetLeastNumbers_Solution1(n,4));
          arrayList=  GetLeastNumbers_Solution1(n1,10);
          arrayList=  GetLeastNumbers_Solution1(n2,4);
            System.out.println("allla");
        }
        static public ArrayList<Integer> GetLeastNumbers_Solution1(int [] input, int k) //利用Treeset直接排序
        {
            ArrayList arrayList= new ArrayList();
            if (input==null||k<=0||k>input.length||input.length<=0)
                return arrayList;
            TreeSet<Integer> treeSet = new TreeSet<>();
            for (int i = 0; i < input.length; i++) {
                treeSet.add(input[i]);
            }
            for (int i=0;i<k;i++)
            {
                arrayList.add(treeSet.pollFirst());
            }
            return  arrayList;
        }
        static public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { //快排，寻找哨兵
            ArrayList arrayList= new ArrayList();
            if (input==null||k<=0||k>input.length||input.length<=0)
                    return arrayList;
            int left = 0;
            int right = input.length-1;
            int index =AdujustArray(input,left,right);
            while (index!=k-1)
            {
                if (index<k-1) {
                    left = index + 1;
                    index=AdujustArray(input,left,right);
                }
                else
                {
                    right =index-1;
                    index= AdujustArray(input,left,right);
                }
            }
            for (int i = 0 ; i<k;i++)
            {
                arrayList.add(input[i]);
            }
            return arrayList;
        }
        public  static  int AdujustArray(int array[], int left , int right)
        {
            int i =left;
            int j= right;
            int x = array[left];
            while (i<j)
            {
                while (array[j]>=x&&i<j)
                    j--;
                if (i<j) {
                    array[i] = array[j];
                    i++;
                }
                while (array[i]<x&&i<j)
                    i++;
                if (i<j) {
                    array[j] = array[i];
                    j--;
                }
            }
            array[i]=x;
            return i;
        }
         static public ArrayList<Integer> GetLeastNumbers_Solution2(int [] input, int k)
        {
            ArrayList arrayList= new ArrayList();
            if (input==null||k<=0||k>input.length||input.length<=0)
                return arrayList;
            int [] array = BuildMaXHeap(input);
            for (int i = array.length-1;i>array.length-1-k;i--)
            {
                int temp = array[0];
                array[0]=array[i];
                array[i]= temp;
                arrayList.add(temp);
                AdjustMaxHeap(array,0,i);
            }
            return  arrayList;
        }
        static   public  int [] BuildMaXHeap(int []array)
        {
            /*
            大根堆如果从一开始计数，ki就是k2i,k(2i+1)的父节点；
            但是数组是从零计数的，个数就是数组长度，父节点下标就是/2再减去一；
             */
            for (int i=(array.length-2)/2;i>=0;i--)
            {
                AdjustMaxHeap(array,i,array.length);
            }
            return  array;
        }
        static    public void  AdjustMaxHeap(int []array , int k,int length)
        {
            int temp = array[k];                            //当前要调整的父节点
            /*
             j是他的子节点，如果继续循环，说明当前节点已经向下移动了了一层
             */
            for (int j=2*k+1;j<length-1;j=2*k+1)
            {
                if (j<length&&array[j]>array[j+1])            //如果右节点比左节点大，就变化下标
                {
                    j++;
                }
                if (temp<=array[j])                                 //父节点大于当前子节点的最大值，说明这个父节点为首的大根堆没有问题
                    break;
                else {
                    array[k] = array[j];
                    k = j;                    //记录父节点更换到的位置，继续下一次的循环
                }
            }
            array[k]= temp;                   //父节点可能会有多次移动，所以最后一次移动结束。再赋值
        }
    }

收获

  1. 一道题用了Treeset解决，快排的哨兵法还有堆排序；说明在数的排序上，还是有很多文章的；
继续跑<br><br>带着赤子的骄傲