leetcode：那些年我遇到过的编程题006：最小的k个数

leetcode：那些年我遇到过的编程题006：最小的k个数
方法一：
首先在一个循环里比较得出arr[]的最小值，然后放进一个新的数组中去，把这个最小值和它对应的序号放进hashmap中，防止重复提取同一个最小值，进行k轮，这个方法我想完就觉得很麻烦，果不其然，测试还可以，但提交就超时了

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        int min = arr[0], order = 0;
        HashMap<Integer,Integer> list = new HashMap<>();
        for(int j = 0;j<k;j++){
            for(int i = 1; i < arr.length;i++){
                if(min>arr[i]&!list.containsKey(i)){
                    min = arr[i];
                    order = i;
                }
            }
            res[j] = min;
            list.put(order,arr[order]);
            min = 10001;
        }
        return res;
    }
}

方法二：直接对arr[]进行排序，排完序取出最小的k个值。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        int min = arr[0], order = 0;
        for(int j = 0;j<k;j++){
            min = arr[j];
            for(int i = j+1; i < arr.length;i++){
                if(arr[i]<min){
                    min = arr[i];
                    arr[i] = arr[j];
                    arr[j] = min;
                }
            }
            res[j] = min;
        }
        return res;
    }
}

这个用时是真的尴尬，时间复杂度应该是O（nk），下面是用java自带的sort排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        Arrays.sort(arr);
        for(int i = 0 ; i <k ; i++){
            res[i] = arr[i];
        }
        return res;
    }
}

比我的快多了哈哈。