面试题40. 最小的k个数

矫情吗；* 2023-07-17 11:17 13阅读 0赞

# 题目： #

[面试题40. 最小的k个数][40. _k]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解： #

## 1. 题解一：调用API ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]

## 2. 题解二：快速排序（首选） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]

## 3. 题解三：大顶堆 ##

保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
    1. 若目前堆的大小小于K，将当前数字放入堆中。
    2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；
       反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。

# 代码： #

## 1. 代码一：调用API ##

/** * code面试题40 */
    import java.util.*;
    
    public class code面试题40 { 
    
        // // 解法一：
        // public static int[] getLeastNumbers(int[] arr, int k) { 
        // Arrays.sort(arr);
        // int res[] = new int[k];
        // for (int i = 0; i < k; i++) { 
        // res[i] = arr[i];
        // }
        // return res;
        // }
    
        // 解法二：
        public static int[] getLeastNumbers(int[] arr, int k) { 
            Arrays.sort(arr);
            return Arrays.copyOfRange(arr, 0, k);
        }
    
        public static void main(String[] args) { 
            int arr[] = {  3, 2, 1 };
            int k = 2;
            int ans[] = getLeastNumbers(arr, k);
            for (int i = 0; i < ans.length; i++) { 
                System.out.print(ans[i] + " ");
            }
            System.out.println();
        }
    }

## 2. 代码二：快速排序（首选） ##

### 2.1 快速排序一（首选） ###

import java.util.*;
    
    public class 面试题40 { 
    
        // 解法三：快速排序一
        public static int[] getLeastNumbers(int[] arr, int k) 
        { 
            quicksort(arr, 0, arr.length - 1);
            return Arrays.copyOfRange(arr, 0, k);
        }
    
        public static void quicksort(int a[], int left, int right)
        { 
            if(left < right)
            { 
                // 获取中轴元素所处的位置
                int mid = partition(a, left, right);
                // 进行分割
                quicksort(a, left, mid - 1);
                quicksort(a, mid + 1, right);
            }
        }
    
        public static int partition(int a[], int left, int right)
        { 
            // 选取中轴元素
            int pivot = a[left];
            int i = left + 1;
            int j = right;
            while(true)
            { 
                // 向右找到第一个大于 pivot 的元素位置
                while(i <= j && a[i] <= pivot)
                { 
                    i++;
                }
                // 向左找到第一个小于 pivot 的元素位置
                while(i <= j && a[j] >= pivot)
                { 
                    j--;
                }
                if(i >= j)
                { 
                    break;
                }
                // 交换两个元素的位置，使得左边的元素不大于pivot,右边的不小于pivot
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
            a[left] = a[j];
            // 使中轴元素处于有序的位置
            a[j] = pivot;
            return j;
        }
    
        public static void main(String[] args) { 
            int arr[] = {  3, 2, 1 };
            int k = 2;
            int ans[] = getLeastNumbers(arr, k);
            for(int i = 0; i < ans.length; i++) 
            { 
                System.out.print(ans[i] + " ");
            }
            System.out.println();        
        }
    }

### 2.2 快速排序二 ###

/** * code面试题40 */
    import java.util.*;
    
    public class code面试题40 { 
    
        // 解法四：快速排序二
        public static int[] getLeastNumbers(int[] arr, int k) { 
            quickSort(arr, 0, arr.length - 1);
            return Arrays.copyOfRange(arr, 0, k);
        }
    
        public static void quickSort(int a[], int left, int right) { 
            if (left < right) { 
                // 获取中轴元素所处的位置
                int mid = partition(a, left, right);
                // 进行分割
                quickSort(a, left, mid - 1);
                quickSort(a, mid + 1, right);
            }
        }
    
        public static int partition(int a[], int left, int right) { 
            int temp = a[left]; // 数组的第一个作为中轴
            while (left < right) { 
                while (left < right && a[right] >= temp) { 
                    right--;
                }
                a[left] = a[right]; // 比中轴小的记录移到低端
                while (left < right && a[left] <= temp) { 
                    left++;
                }
                a[right] = a[left]; // 比中轴大的记录移到高端
            }
            a[left] = temp; // 中轴记录到位
            return left; // 返回中轴的位置
        }
    
        public static void main(String[] args) { 
            int arr[] = {  3, 2, 1 };
            int k = 2;
            int ans[] = getLeastNumbers(arr, k);
            for (int i = 0; i < ans.length; i++) { 
                System.out.print(ans[i] + " ");
            }
            System.out.println();
        }
    }

## 3. 代码三：大顶堆 ##

// 解法五：大顶堆
    public static int[] getLeastNumbers(int[] arr, int k) { 
        if(k == 0 || arr.length == 0) 
        { 
            int temp[] = new int[0];
            return temp;
        }
        // 默认是小根堆，实现大根堆需要重写一下比较器。
        PriorityQueue<Integer> queue = new PriorityQueue<>((n1, n2) -> n2 - n1);
        for(int i = 0; i < arr.length; i++)
        { 
            if(queue.size() < k)
            { 
                queue.offer(arr[i]);
            }
            // 如果 新数 < 堆顶元素，则删除堆顶，加入新数入堆
            else if(arr[i] < queue.peek())
            { 
                queue.poll();
                queue.offer(arr[i]);
            }
        }
    
        // 返回堆中的元素
        int res[] = new int[k];
        for(int i = 0; i < k && !queue.isEmpty(); i++)
        { 
            res[i] = queue.poll();
        }
        return res;
    }

# 参考： #

1.  [最小的k个数][k]
2.  [4种解法秒杀TopK（快排/堆/二叉搜索树/计数排序）][4_TopK]
3.  [Top K 的两种经典解法（堆/快排变形）与优劣比较][Top K]
4.  [从一场微软面试中领悟到的一些东西][Link 1]
5.  [C++手撕堆排序 一文看会堆排序][C_]
6.  [最小的k个数简单解题][k 1]
7.  [Java sort()数组排序（升序和降序）][Java sort]
8.  [Java Collections类操作集合详解][Java Collections]
9.  [关于Java中的Arrays.copyOfRange()方法][Java_Arrays.copyOfRange]
10. [【排序算法】快速排序原理及Java实现][Java]
11. [大顶堆和小顶堆-java][-java]

# 快速排序参考： #

1.  [必学十大经典排序算法，看这篇就够了(附完整代码动图优质文章)][Link 2]
2.  [【漫画】不要再问我快速排序了][Link 3]
3.  [必须知道的八大种排序算法【java实现】][java]

## 1. 快速排序一：（首选） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]

## 2. 快速排序二： ##

![在这里插入图片描述][20200321223640170.png]  
快速排序的示例：  
（a）一趟排序的过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]  
（b）排序的全过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 8]  
**算法：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 11]

[40. _k]: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: /images/20230528/ce5a329b7ee645c18087a0e0f6265f3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/ce5c3a54fc1e4bfb85b01c77d1e0317c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: /images/20230528/6d4df9ae69ef4ebc95c31030f605717a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: /images/20230528/d82032762e79464483a690709db9d5a2.png
[k]: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/
[4_TopK]: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/
[Top K]: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/tu-jie-top-k-wen-ti-de-liang-chong-jie-fa-you-lie-/
[Link 1]: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/wei-ruan-mian-shi-jiao-xun-x-by-jerry_nju/
[C_]: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/shou-si-dui-pai-xu-yi-wen-kan-hui-dui-pai-xu-by-ti/
[k 1]: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-jian-dan-jie-ti-by-hzs-5/
[Java sort]: http://c.biancheng.net/view/925.html
[Java Collections]: http://c.biancheng.net/view/6884.html
[Java_Arrays.copyOfRange]: https://blog.csdn.net/babylorin/article/details/67637454
[Java]: https://blog.csdn.net/jianyuerensheng/article/details/51258374
[-java]: https://juejin.im/post/5d0654fd51882554d63127d1
[Link 2]: https://zhuanlan.zhihu.com/p/57088609
[Link 3]: https://mp.weixin.qq.com/s?__biz=Mzg2NzA4MTkxNQ==&mid=2247485191&idx=1&sn=45a43bd77495566db53b419ae82136f5&source=41#wechat_redirect
[java]: https://www.jianshu.com/p/8c915179fd02
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: /images/20230528/9b55c7adcf6d4d5989867832fe2283ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]: /images/20230528/c109f8ee60aa4d4c8e6fab0c9b804f2e.png
[20200321223640170.png]: /images/20230528/acdb56ab1ccd447ca4d265cf54453099.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]: /images/20230528/615c40862003437cb105871f5a6482b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 7]: /images/20230528/ed5d156238bb4b1cbe001c63c264d3f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 8]: /images/20230528/790e1dbd24424bb9a7489a8338523076.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 9]: /images/20230528/1b3daae7e4804c468751e29d44d56da0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 10]: /images/20230528/d59995a90df542af852834dfd173f6d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 11]: /images/20230528/4fdbd9136a394ef69b3b2cdb77638639.png