[数据结构与算法]【栈队列堆】【打卡82天】《剑指Offer》2刷：JZ40 最小的K个数

1、题目描述

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

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

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

?2、算法分析

先对数组排序，然后取前k个数组的值存储到集合中。

Arrays.sort(array)：排序数组元素，从大到小。

3、代码实现

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        Arrays.sort(input);
        ArrayList<Integer> result = new ArrayList<>();
        if(input == null){
            return result;
        }
        if(k < input.length){
            for(int i = 0;i < k;i++){
                result.add(input[i]);
            }
        }else{
            for(int j = 0;j < input.length;j++){
                result.add(input[j]);
            }
        }
        return result;
    }
}