找出数组中K个最小数问题

╰半夏微凉° 2023-07-17 06:52 22阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

题目分析：

1）暴力算法：

2）优化算法(堆排序)：

3）最优算法(快速排序)

源码地址：

--------------------

### 题目描述： ###

输入整数数组 `arr` ，找出其中最小的 `k` 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

**示例 1：**

输入：arr = [3,2,1], k = 2
    输出：[1,2] 或者 [2,1]

**示例 2：**

输入：arr = [0,1,2,1], k = 1
    输出：[0]

**限制：**

*  `0 <= k <= arr.length <= 10000`
 *  `0 <= arr[i] <= 10000`

--------------------

## 题目分析： ##

首先这个问题，就是一个普通的排序问题： 排序分为选择排序，冒泡排序，插入排序，快速排序，基数排序，归并排序等;可以解决该问题。

![849589-20171015233043168-1867817869.png][]

### 1）暴力算法： ###

首先对于解决本题目，先想到使用冒泡排序，冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 它的思路是先将数组进行排序，然后取前面k个值，最直接的思路：

*  比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
 *  针对所有的元素重复以上的步骤，除了最后一个；
 *  重复步骤1~3，直到排序完成。

排序完成之后再选取前面k个值：

/**
         * 获取最小多个值;快速排序
         *
         * @param arr 数组
         * @param k   k个数
         * @return 数组
         */
        public int[] getLeastNumbers(int[] arr, int k) {
            if (arr.length == 0)
                return arr;
            for (int i = 0; i < arr.length; i++)
                for (int j = 0; j < arr.length - 1 - i; j++)
                    if (arr[j + 1] < arr[j]) {
                        int temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                    }
            return Arrays.stream(arr).limit(k).toArray();
        }

时间复杂度：O(n)

空间复杂度：O(1)

--------------------

### 2）优化算法(堆排序)： ###

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

*  将堆顶元素R\[1\]与最后一个元素R\[n\]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R\[1,2…n-1\]<=R\[n\]；
 *  由于交换后新的堆顶R\[1\]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R\[1\]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

这种方法相对于上一种方法有一定的优化。

/**
         * 获取最小多个值,利用优先队列
         *
         * @param arr 数组
         * @param k   k个数
         * @return 数组
         */
        public int[] getLeastNumbers2(int[] arr, int k) {
            PriorityQueue<Integer> priorityQueue = new PriorityQueue();
            List<Integer> list = new ArrayList<>();
            for (int num : arr) {
                priorityQueue.add(num);
                if (priorityQueue.size() > arr.length - k) {
                    list.add(priorityQueue.poll());
                }
            }
            return list.stream().mapToInt(e -> Integer.valueOf(e)).toArray();
        }

时间复杂度：O（n.logn）

空间复杂度：O（n）

--------------------

### 3）最优算法(快速排序) ###

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

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

/**
         * 获取最小多个值 ,利用快速排序方法
         *
         * @param arr 数组
         * @param k   k个数
         * @return 数组
         */
        public int[] getLeastNumbers3(int[] arr, int k) {
            int len = arr.length;
            if (k == 0 || k > len) {
                return new int[0];
            }
            int target = k - 1;
            int left = 0;
            int right = len - 1;
            while (true) {
                int index = partition(arr, left, right);
                if (index == target) {
                    int[] res = new int[k];
                    for (int i = 0; i < k; i++) {
                        res[i] = arr[i];
                    }
                    return res;
                } else if (index < target) {
                    // 下一轮搜索区间在 [index + 1, right]
                    left = index + 1;
                } else {
                    // 下一轮搜索区间在 [left, index - 1]
                    right = index - 1;
                }
            }
        }
    
        /**
         * 进行分区操作
         *
         * @param arr   数组
         * @param left  左边
         * @param right 右边
         * @return 下标
         */
        private int partition(int[] arr, int left, int right) {
            int pivot = arr[left];
            int index = left;
            for (int i = left + 1; i <= right; i++) {
                if (arr[i] < pivot) {
                    index++;
                    swap(arr, index, i);
                }
            }
            swap(arr, left, index);
            return index;
        }
    
        /**
         * 交换数据中元素的位置
         *
         * @param arr 数组
         * @param i   位置i
         * @param j   位置j
         */
        private void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

时间复杂度：O（n）

空间复杂度：O（n）

--------------------

## 源码地址： ##

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[849589-20171015233043168-1867817869.png]: /images/20230528/4070b1b523104c7dbed9f9a8246efe4d.png
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode