29、最小的K个数

一、题目

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

二、解法

 import java.util.ArrayList;

 public class Solution {

     public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {

         // 运行时间：35ms 占用内存：503k

         ArrayList<Integer> minNs = new ArrayList<Integer>();

         if (k == 0 || k > input.length)

             return minNs;

         int[] m = new int[k];

         // 先把前k个存储到结果

         for (int j = 0; j < k; j++) {

             m[j] = input[j];

         }

         int maxIndex = 0;// 最大下标

         boolean findMax = true;// 默认每次都要找到最大的

         for (int i = k; i < input.length; i++) {

            if(findMax)

              maxIndex = 0;

             // 开始比较，从第k个开始，每次找最大的替换出来

                 for (int d = 1; d < k; d++) {

                     if (m[d] > m[maxIndex]) {

                         maxIndex = d;

                     }

             }

             // 找到后 比较 如果当前值input[k]比 m中的最大值还小，那么替换

             if (input[i] < m[maxIndex]) {

                 m[maxIndex] = input[i];

                 findMax = true;

             }else {

                 findMax = false;

             }

         }

         for (int i = 0; i < k; i++) {

             // 添加到minNs中

             minNs.add(m[i]);

         }

         return minNs;

     }

 }