最小的 K 个数

题目描述

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

解题思路

动态规划。

用前 k 个数当做当前最优解，每次更新一个数，去除最大值，直到遍历完数组，获得全局最优解。

代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (input.length < k)
            return ret;
        for (int i = 0; i < k; i++)
            ret.add(input[i]);
        for (int i = k; i < input.length; i++)
            findMin(ret, input[i]);
        return ret;
    }
    
    private void findMin(ArrayList<Integer> list, int min) {
        for (int i = list.size()-1; i >= 0; i--) {
            if (list.get(i) > min) {
                int tmp = min;
                min = list.get(i);
                list.remove((int)i);
                list.add(tmp);
            }
        }
    }
}