前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >面试如戏,全靠 “演技”

面试如戏,全靠 “演技”

作者头像
五分钟学算法
发布2022-04-08 16:05:08
4890
发布2022-04-08 16:05:08
举报
文章被收录于专栏:五分钟学算法

大家好,我是吴师兄。

众所周知,Top K 问题是面试中的常客,一般有两种解法,一种解法使用堆,另一种解法借鉴快速排序的思想。

如果在面试的时候问到了Top K 问题,同时你又掌握了这两种解法,请憋住笑

遇到原题,更加需要好好发挥。

  • 和面试官沟通清楚问题的细节
  • 是否可以修改原数组
  • 数据量大不大

因为,不同的条件会决定这两种解法哪种更好一些。

面试如戏,你需要在这场面试中让面试官看到你思考问题的方式

如果一看到原题,你就噼里啪啦的背出答案,说不定面试官就一皱眉头:大意了,给他出原题了,那我得重新出一道难题

结果给你一道你没见过的难题,翻车了!

所以,切记,面试遇到原题,请好好表演,尽可能的拉扯时间,让面试官认为你解决问题的思路没问题

今天,就带大家来学习一道非常经典的Top K 问题,同时使用快速排序的思想去处理,好好掌握,方可演戏!

先看题目描述:

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

这道题目最简单粗暴的方法当然是将数组 arr 按照从小到大的顺序整体排序之后,获取数组的前 k 个数就行。

而整体排序的算法有很多种选择,比如冒泡、选择、快速、堆排序等等。

这种暴力解法肯定不是面试官想要的回答,因为我们没有利用好题目的全部条件。

再读一下这句话:找出其中最小的 k 个数

这句话隐藏着以下几个意思:

  • 1、找出的这 k 个数并不需要按照顺序排列。
  • 2、如果一开始就知道某个数不在这 k 个数中,完全可以将它丢到一旁。

也就意味着,在排序过程中,我们可以去不断的缩小排序的区间,这里我们借助快速排序的代码,稍微的改动几行就完成了这道题目。

具体操作如下:

  • 1、以当前区间的第一个元素为基准元素 pivot,根据快速排序的操作,将当前区间划分为了三个区间。
    • 1、左侧区间均是小于等于基准元素 pivot 的元素
    • 2、中间区间均是等于基准元素 pivot 的元素
    • 3、右侧区间均是大于等于基准元素 pivot 的元素
  • 2、对比基准元素 pivot 所在的下标 index 与 k 的关系
    • 1、index 小于 k,说明从 0 到 index 这个左侧区间中的元素不足 k 个,那么最小的 k 个数肯定部分是在这个区间,还需要继续在右侧区间中去寻找出一部分元素来填充,因此对对右侧区间进行快速排序即可
    • 2、index 等于 k,说明从 0 到 index 这个区间中的所有元素就是那些最小的 k 个数,将其返回。
    • 3、index 大于 k,说明从 0 到 index 这个左侧区间中的元素超过了 k 个,那么最小的 k 个数肯定是都在在这个区间,而中间、右侧区间均可以不去处理,只需要继续对左侧区间进行快速排序即可,找到那 k 个数。

最后,结合分析迅速写出代码。

代码语言:javascript
复制
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {

        if (k == 0 || arr.length == 0) {
            return new int[0];
        }

        // 执行快速排序操作,定位找到下标为 k - 1 的那个元素
        return quickSort(arr,0,arr.length - 1,k - 1);
    }


    // 函数传入待排序数组 nums
    // 排序区间的左端点 left
    // 排序区间的右端点 right
    private int[] quickSort(int[] nums,int left, int right , int index){

        // 调用函数 partition,将 left 和 right 之间的元素划分为左右两部分
        int mid = partition(nums,left,right);
        
        // 如果 mid 下标恰巧为 index,那么找到了最小的 k 个数
        if (mid == index) {
            // 直接返回
            return Arrays.copyOf(nums, mid + 1);
        
        // 如果 mid 下标大于 index,那么说明需要在左侧元素中去切分
        }else if( mid > index ){

            // 对 mid 左侧的元素进行快速排序
            return quickSort(nums,left,mid - 1, index );
        }else{

            // 对 mid 右侧的元素进行快速排序
            return quickSort(nums,mid + 1,right, index );
        }

    }

    private int partition(int[] nums, int left ,int right){

        // 经典快速排序的写法
        // 设置当前区间的第一个元素为基准元素
        int pivot = nums[left];

        // left 向右移动,right 向左移动,直到 left 和 right 指向同一元素为止
        while( left < right ){

            // 只有当遇到小于 pivot 的元素时,right 才停止移动
            // 此时,right 指向了一个小于 pivot 的元素,这个元素不在它该在的位置上
            while( left < right && nums[right] >= pivot ){
                // 如果 right 指向的元素是大于 pivot 的,那么
                // right 不断的向左移动
                right--;
            }

            // 将此时的 nums[left] 赋值为 nums[right]
            // 执行完这个操作,比 pivot 小的这个元素被移动到了左侧
            nums[left] = nums[right];


            // 只有当遇到大于 pivot left 才停止移动
            // 此时,left 指向了一个大于 pivot 的元素,这个元素不在它该在的位置上
            while( left < right && nums[left] <= pivot){
                // 如果 left 指向的元素是小于 pivot 的,那么
                // left 不断的向右移动
                left++;
            }

            // 将此时的 nums[right] 赋值为 nums[left]
            // 执行完这个操作,比 pivot 大的这个元素被移动到了右侧
            nums[right] = nums[left];

        }

        // 此时,left 和 right 相遇,那么需要将此时的元素设置为 pivot
        // 这个时候,pivot 的左侧元素都小于它,右侧元素都大于它
        nums[left] = pivot;

        // 返回 left
        return left;

    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-03-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 五分钟学算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档