专栏首页小浩算法漫画:美团面试题(TOPK:求第K个最大的元素)

漫画:美团面试题(TOPK:求第K个最大的元素)

今天是小浩算法“365刷题计划”第70天。分享一道美团面试题。话不多说,直接看题。

01 PART

第K个最大元素

这个题目的变形很多,比如找 "前 K 个高频元素"、 "数据流中的第K大元素" 、"最接近原点的 K 个值" 等等等等。

第215题:在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4

输出: 4

02 PART

大顶堆

堆在算法题目中的应用主要包括以下几点:

  • TopK 问题 (尤其是大数据处理)
  • 优先队列
  • 利用堆求中位数

这种题目,从个人来讲,我一般是比较偏好使用堆来做的。毕竟大小顶堆,刚好有着与本类题型契合的特性。如果对堆不太熟悉的话,可以先看下这篇文章:

漫画:BAT必考题目 (最小的k个数)

那本题如何使用堆来做呢?假若我们的数组为[3,2,1,5,6,4],k=2,我们对其构造一个小顶堆(每个结点的值均不大于其左右孩子结点的值,堆顶元素为整个堆的最小值),整个过程是这样:

  • 构造一个小顶堆,依次将元素放入堆中,并保证堆中元素为k。
  • 如果当前元素小于堆顶元素,那基本就不用看了(因为我们要找的是 排序后的第 k 个最大的元素)
  • 自然,如果我们遇到比堆顶元素大的元素,就把它放入到堆中。
  • 重复上面的步骤:

然后根据分析,完成代码(今天就不手撕堆了,因为之前已经手撕过了。同时这里给大家一个建议,如果面试的时候,遇到这种TOPK的问题,假如特别有把握,肯定得手撕数据结构,一定会加分。但是如果没有把握,那就先用API实现,以 BugFree 为目标吧!)

//JAVA
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minQueue = new PriorityQueue<>(k);
        for (int num : nums) {
            if (minQueue.size() < k || num > minQueue.peek()) {
                minQueue.offer(num);
            }
            if (minQueue.size() > k) {
                minQueue.poll();
            }
        }
        return minQueue.peek();
    }
}

我也不知道为啥,Python永远就是这么牛X,朴实无华且枯燥!

//python
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]

注:python可以使用heapq.nlargest 或 heapq.nsmallest,来找出某个集合中找出最大或最小的N个元素。

//python
>>> import heapq
>>> nums=[1,8,2,23,7,-4,18,23,42,37,2]
>>> print(heapq.nlargest(3,nums))
[42, 37, 23]
>>> print(heapq.nsmallest(3,nums))
[-4, 1, 2]

郑重申明(读我的文章必看):

  • 本系列所有教程都不会用到复杂的语言特性,大家无须担心没有学过相关语法,算法思想才是最重要的!
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode进行过测试运行。

03 PART

快排

快速排序(Quicksort)是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

那对于本题,我们就是使用快排的思想,选定一个基准值,把比基准值大的放在基准值的右边,把基准值小的放在基准值的左边。若基准值刚好位于倒数第k个数,则基准值为目标值;反之,则递归处理目标值所处的那一部分数组。

//go
func findKthLargest(nums []int, k int) int {
    idx := quickSort(0, len(nums) - 1, len(nums) - k, nums)
    return nums[idx]
}

func quickSort(l, r, pos int, nums []int) int {
    povit_idx := partition(l, r, nums)
    if pos == povit_idx {
        return povit_idx
    } else if pos > povit_idx {
        return quickSort(povit_idx + 1, r, pos, nums)
    } else {
        return quickSort(l, povit_idx - 1, pos, nums)
    }
}

func partition(l, r int, nums []int) int {
    s := l
    povit_value := nums[l]
    for l < r {
        for ;l < r && nums[r] >= povit_value; {
            r--
        }
        for ;l < r && nums[l] <= povit_value; {
            l++
        }
        if l < r {
            nums[l] = nums[r] ^ nums[l]
            nums[r] = nums[l] ^ nums[r]
            nums[l] = nums[r] ^ nums[l]
        }
    }
    nums[s] = nums[l]
    nums[l] = povit_value
    return l
}

整个快排的核心,其实就partition。partition 有 单向扫描,双向扫描 等多种写法。上面的代码,大家可以参考参考,看不懂也没关系,我后面是会单独安排一个快排的系列篇来进行讲解的,到时候一堆图解砸进来,保准你看的醍醐灌顶!

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:经典鹅厂面试题(2Sum,3Sum,4Sum)

    该题为 二数之和 的进阶版本,当然还有一个进阶版本为 四数之和。我们将会一一进行分析!

    程序员小浩
  • 漫画:常考的荷兰国旗问题你还不会吗?(初级)

    "荷兰国旗问题" 是计算机科学中的一个经典题目,它是由Edsger Dijkstra提出的。荷兰国旗由红、白、蓝三色组成。

    程序员小浩
  • 漫画:经典鹅厂面试题(4sum - nSum)

    第18题:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + ...

    程序员小浩
  • LintCode 633. 寻找重复的数(这个题要复习)

    给出一个数组 nums 包含 n + 1 个整数,每个整数是从 1 到 n (包括边界),保证至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

    Michael阿明
  • 【leetcode刷题】20T17-下一个排列

    https://leetcode-cn.com/problems/next-permutation/

    木又AI帮
  • 「图解」缺失的第一个正数

    这道题使用桶排序的思路,即 “一个萝卜一个坑”,就可以解决。可以就使用题目中的例子,在纸上写写画画,就能得出思路,只不过在编码上需要注意一些细节。

    五分钟学算法
  • Array - 508. Wiggle Sort

    Given an unsorted array nums, reorder it in-place such that

    用户5705150
  • 【剑指Offer】调整数组顺序使奇数位于偶数前面

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

    小新哟
  • 数据结构算法操作试题(C++/Python)——四数之和

    数据结构算法操作试题(C++/Python):数据结构算法操作试题(C++/Python)——目录

    莫斯
  • python-快速排序

    核心思想:取一个初始值,将数组中比该值小的放在其左边,比其大的放在右边, 再对左、右子数组进行相同操作,直到数组排好序。

    绝命生

扫码关注云+社区

领取腾讯云代金券