最小的 K 个数

本贴最后更新于 2231 天前,其中的信息可能已经时移世易

题目描述

输入 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);
            }
        }
    }
}

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...