本文共 4869 字，大约阅读时间需要 16 分钟。

剑指offer打卡Day16：最小的k个数（优先队列与快速排序）

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

示例

输入

[4,5,1,6,2,7,3,8],4

返回值

[1,2,3,4]

解析：

• 万物皆可用暴力法破解：

  • 对数组进行判断，（判断非空与 k>input.length 或者K==0 等情况）
  • 对数组进行排序，默认排序都是从小到大进行排序
  • 遍历数组，同时记得维护非重和count计数(以k为标准)
  • 将数组元素存入Arraylist并返回

• 暴力法确实可以解决问题，但是老是靠暴力解决不了问题啊，就跟现在的工作铲屎一样学不了东西

• 查阅资料发现可以用优先队列来完成这题

• 优先队列PriorityQueue

  • 标准定义：

    PriorityQueue类在Java1.5中引入。PriorityQueue是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。

  • 作用：

    优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素，C++的优先队列每次取最大元素）。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator，类似于C++的仿函数）。

  • 举两个例子：

    1. 作业系统中的调度程序，当一个作业完成后，需要在所有等待调度的作业中选择一个优先级最高的作业来执行，并且也可以添加一个新的作业到作业的优先队列中。
    2. 每日交易时段生成股票报告的应用程序中，需要处理大量数据并且花费很多处理时间。客户向这个应用程序发送请求时，实际上就进入了队列。我们需要首先处理优先客户再处理普通用户。在这种情况下，Java的PriorityQueue(优先队列)会很有帮助。

• 快速排序：

  • 快速排序（QuickSort ）是常用到的效率比较高的一种排序算法，在面试过程中也经常提及，出了冒泡再复习下这个快排算法。

  • 执行步骤总结：

    • 从数列中挑出一个元素，称为 “基准”（pivot）;

    • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

    • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

      –作者：五分钟学算法

  • 图解执行步骤：

    • 以数列[6,1,2,7,9,3,4,5,10,8]为例

    • 具体过程如下图：

    

    • 配合图片讲解算法：

      • Step1：

        • 以数列首位(index == 0)为基准(pivot)，right为最后一位(index == arr.length-1)，left为第二位(index == 1)，开始遍历；

        • 从right开始，向左(index–)开始寻找比pivot小的元素，移动一位后left也开始向右(index++)移动寻找比pivot大的元素，若找到了他们要的便会停止移动，并交换L与R

        • 如图：

          • 5与7交换，4与9交换

        • 当遍历至left == right之后，(L,R)与pivot交换

        • 执行完毕后变为：

          [3,1,2,5,4,6,9,7,10,8]

          此时发现以原pivot（6）为分界线，做左边的数列都小于6，右边的数列都大于6

      • Step2：

        • 将数列[3,1,2,5,4,6,9,7,10,8]以6分成左右两个小数列（命名为A、B）
        • 并分别对两个小组小数列进行类似Step1的操作
        • A => [1,2,3,4]
        • B => [7,8,9,10]

      • Step3:

        • 合并起来即可

      • 综上，其实就是一直在重复Step1上的步骤：找pivot与遍历，因此可以用递归来实现

  • 代码解析：

    //Java 代码实现public class QuickSort implements IArraySort {           @Override    public int[] sort(int[] sourceArray) throws Exception {               // 对 arr 进行拷贝，不改变参数内容        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);        return quickSort(arr, 0, arr.length - 1);    }    private int[] quickSort(int[] arr, int left, int right) {               if (left < right) {                   int partitionIndex = partition(arr, left, right);            quickSort(arr, left, partitionIndex - 1);            quickSort(arr, partitionIndex + 1, right);        }        return arr;    }    private int partition(int[] arr, int left, int right) {               // 设定基准值（pivot）        int pivot = left;        int index = pivot + 1;        for (int i = index; i <= right; i++) {                   if (arr[i] < arr[pivot]) {                       swap(arr, i, index);                index++;            }        }        swap(arr, pivot, index - 1);        return index - 1;    }    private void swap(int[] arr, int i, int j) {               int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }}

解答：

//万能的暴力解法:(此处用最基础的冒泡排序)public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {       ArrayList<Integer> list = new ArrayList<Integer>();    //判空或者超出范围的数字    if(k > input.length || k == 0 ){           return list;    }    //先排序，再找出不重复的最小前k个    //Arrays.sort(input);    BubbleSort(input);    int count = 0;    for (int i = 0; i < input.length; i++) {           if (list.contains(input[i])){               continue;        }else {               list.add(input[i]);            count++;        }        if (count == k){               break;        }    }    return list;}public  void BubbleSort(int[] arr) {       int temp;//定义一个临时变量    for(int i=0;i<arr.length-1;i++){   //冒泡趟数        for(int j=0;j<arr.length-i-1;j++){               if(arr[j+1]<arr[j]){                   temp = arr[j];                arr[j] = arr[j+1];                arr[j+1] = temp;            }        }    }}//用堆排序解题：public ArrayList<Integer> GetLeastNumbers_Solution_withPriorityQueue(int[] input, int k) {       ArrayList<Integer> result = new ArrayList<Integer>();    int length = input.length;    if(k > length || k == 0){           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 < 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 integer : maxHeap) {           result.add(integer);    }    return result;}

参考与扩展：

1. 最近在刷力扣题的时候不止一次看到过这个PriorityQueue，他的优良特性可以帮助我们解决大量的题目。这篇文章从用法、原理、源码以及力扣实际题目的角度进行一个全面的分析。

2. Java中PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。本文从Queue接口函数出发，结合生动的图解，深入浅出地分析PriorityQueue每个操作的具体过程和时间复杂度，将让读者建立对PriorityQueue建立清晰而深入的认识。

3. 队列是遵循先进先出（First-In-First-Out）模式的，但有时需要在队列中基于优先级处理对象。

4. 高快省的排序算法

   有没有既不浪费空间又可以快一点的排序算法呢？那就是“快速排序”啦！光听这个名字是不是就觉得很高端呢。