题解 | #最小的K个数#

JZ29 最小的K个数

描述
给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
0 <= k <= input.length <= 10000
0 <= input[i] <= 10000

思路就是先保存前k个数为一个数组，然后记录数组中最大的数，从第k+1个数开始比较，如果小于最大的数，就进行交换，一直循环到最后一个数。

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> minK = new ArrayList<Integer>();
        if(k == 0) return minK;
        for(int i = 0; i < k; i++){
            minK.add(input[i]);
        }

        int maxIndex = findMax(minK);
        for(int i = k; i < input.length; i++){
            if(input[i] < minK.get(maxIndex)){
                minK.set(maxIndex, input[i]);
                maxIndex = findMax(minK);
            }
        }
        return minK;
    }

    public static int findMax(ArrayList<Integer> input){
        int maxIndex = 0;
        for(int i = 1; i < input.size(); i++){
            if(input.get(i) > input.get(maxIndex)){
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}