NC119 最小的K个数

题目链接：https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf

题目描述

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

数据范围：0≤k,n≤10000，数组中每个数的大小0≤val≤1000

要求：空间复杂度 O(n) ，时间复杂度 O(nlogn)

示例 1：

输入：[4,5,1,6,2,7,3,8],4 
返回值：[1,2,3,4]
说明：返回最小的4个数即可，返回[1,3,2,4]也可以

示例 2：

输入：[1],0
返回值：[]

示例 3：

输入：[0,1,2,1,2],3
返回值：[0,1,1]

解题代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.ArrayList;

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

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为: 2022/07/10 22:06:37