JZ29 最小的K个数

• 思路：
• • 方法一：重建一个优先队列，将数组中的k个数加入队列，如果数组中的元素小于队列中的头元素，队列进行poll操作，然后加入数组元素
• • 方法二：

        //使用快排(快排需要找基准)进行前k项排序
            //思路：对于数组[l, r]一次快排partition过程可得到，[l, p), p, [p+1, r)三个区间,
            //[l,p)为小于等于p的值, [p+1,r)为大于等于p的值。
            //1、如果[l,p), p，也就是p+1个元素（因为下标从0开始），如果p+1 == k, 找到答案
            //2、如果p+1 < k, 说明答案在[p+1, r)区间内，
            //3、如果p+1 > k , 说明答案在[l, p)内

• 时间：2021年8月17号

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


public class Solution {
    int[] nums;
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //方法一：
        //思路：重建一个优先队列，将数组中的k个数加入队列，如果数组中的元素小于队列中的头元素，队列进行poll操作，然后加入数组元素
            //时间复杂度：O(nlogk) 空间复杂度：O(k)
        ArrayList<Integer> ans = new ArrayList<>();

        if (k == 0)
            return ans;

        /* PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer n1, Integer n2) {
                return n2 - n1;//队列中的最大值在头顶
            }
        });
        int count = 0; //记录队列中的数据个数
        for (int i = 0; i < input.length; i++) {
            if (count < k) {
                queue.add(input[i]);
                count++;
            } else {
                if (input[i] < queue.peek()) {
                    queue.poll();
                    queue.add(input[i]);
                }
            }
        }

        while (!queue.isEmpty()) {
            ans.add(queue.poll());
        }

        return ans; */

        //方法二：
        //使用快排(快排需要找基准)进行前k项排序
            //思路：对于数组[l, r]一次快排partition过程可得到，[l, p), p, [p+1, r)三个区间,
            //[l,p)为小于等于p的值, [p+1,r)为大于等于p的值。
            //1、如果[l,p), p，也就是p+1个元素（因为下标从0开始），如果p+1 == k, 找到答案
            //2、如果p+1 < k, 说明答案在[p+1, r)区间内，
            //3、如果p+1 > k , 说明答案在[l, p)内
        //下面的结果并没有将数组进行处理
        /* nums = input;
        int l = 0, r = input.length;
        while (l < r) {
            int p = partition(l, r);
            System.out.println(p);
            if (p+1 == k) {
                for (int i = 0; i < k; i++) {
                    ans.add(nums[i]);
                }
                return ans;
            } else if (p+1 < k) {
                l = p + 1;
            } else {
                r = p;
            }
        }

        return ans;*/

        //方法三：
        for (int i = 0; i < Math.min(input.length - 1, k); i++) {
            for (int j = i + 1; j < input.length; j++) {
                if (input[i] > input[j]) {
                    int temp = input[i];
                    input[i] = input[j];
                    input[j] = temp;
                }
            }

        }
        for (int i = 0; i < k; i++) {
            ans.add(input[i]);
        }
        return ans;
    }

    public int partition(int l, int r) {
        int pivot = nums[r-1];
        int i = l;
        for (int j = l; j < r-1; j++) {
            if (nums[j] < pivot) {
                swap(nums[i++], nums[j]);
            }
        }
        swap(nums[i], nums[r-1]);
        return i;
    }

    public void swap(int num1, int num2) {
        int temp = num1;
        num1 = num2;
        num2 = temp;
    }    
}