class Solution {
    //2.快排
    public List<Integer> getLeastNumbers_Solution(int [] input, int k) {
        if(k <= 0 || input.length == 0) return new ArrayList<Integer>();
        return partition(input, 0, input.length - 1, k - 1);
    }

    private List<Integer> partition(int[] nums, int st, int ed, int k ) {
        int left = st, right = ed;
        int p = nums[st];
        while(left < right) {
            while(left < right && nums[right] >= p) right--;
            if(left < right) nums[left++] = nums[right];
            while(left < right && nums[left] <= p) ++left;
            if(left < right) nums[right--] = nums[left];
        }
        nums[left] = p;
        if(left == k) {
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i <= left; i++) {
                list.add(nums[i]);
            }
            Collections.sort(list);
            return list;
        }else if(left > k) {
            return partition(nums, st, left - 1, k);
        }else {
            return partition(nums, left + 1, ed, k);
        }

    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    //1.最小堆Time:O(nlgN) Space:O(N)
    public List<Integer> getLeastNumbers_Solution1(int [] input, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        for(int val : input) {
            queue.add(val);
            if(queue.size()>k){
                queue.poll();
            }
        }
        LinkedList<Integer> ans = new LinkedList<>();
        while(!queue.isEmpty()){
            ans.addFirst(queue.poll());
        }
        return ans;
    }
}