[每日一道小算法（六十）][數組] 最小的K個數（劍指offer）

前言：

今天最後一道題，實作很簡單。但是想要降低時間複雜度，應該選用什麼樣的方法。

題目描述

解題思路

代碼樣例

Arrays.sort排序 可以AC

package com.asong.leetcode.GetLeastNumbers_Solution;

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

/**
 * 最小的k個數
 * 輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,。
 */
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(input==null||input.length==0||k<0||k>input.length)
        {
            return res;
        }
        Arrays.sort(input);
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }
}      

最大堆實作

package com.asong.leetcode.GetLeastNumbers_Solution;

import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * 最小的k個數  大頂堆實作 比這個樹大抛棄，小則 替換。
 */
public class Solution1 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(input == null || input.length == 0 || k==0 || k>input.length)
        {
            return result;
        }
        //建立大頂堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < input.length; i++) {
            if(maxHeap.size() != k)
            {
                maxHeap.offer(input[i]);
            }else if(maxHeap.peek()>input[i]){
                Integer temp = maxHeap.poll();
                temp = null;
                maxHeap.offer(input[i]);
            }
        }
        for (Integer i:maxHeap
             ) {
            result.add(i);
        }
        return result;
    }
}