Loading [MathJax]/jax/output/CommonHTML/jax.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【面试高频题】难度 1.5/5,多解法经典面试题

【面试高频题】难度 1.5/5,多解法经典面试题

作者头像
宫水三叶的刷题日记
发布于 2022-12-30 08:37:06
发布于 2022-12-30 08:37:06
25300
代码可运行
举报
运行总次数:0
代码可运行

题目描述

这是 LeetCode 上的「215. 数组中的第K个最大元素」,难度为「中等」

Tag : 「树状数组」、「二分」、「优先队列(堆)」、「快速选择」

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n)的算法解决此问题。

示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: [3,2,1,5,6,4], k = 2

输出: 5

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: [3,2,3,1,2,4,5,5,6], k = 4

输出: 4

提示:

值域映射 + 树状数组 + 二分

代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    int M = 10010, N = 2 * M;
    int[] tr = new int[N];
    int lowbit(int x) {
        return x & -x;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    void add(int x) {
        for (int i = x; i < N; i += lowbit(i)) tr[i]++;
    }
    public int findKthLargest(int[] nums, int k) {
        for (int x : nums) add(x + M);
        int l = 0, r = N - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (query(N - 1) - query(mid - 1) >= k) l = mid;
            else r = mid - 1;
        }
        return r - M;
    }
}

优先队列(堆)

另外一个容易想到的想法是利用优先队列(堆),由于题目要我们求的是第 k大的元素,因此我们建立一个小根堆。

根据当前队列元素个数或当前元素与栈顶元素的大小关系进行分情况讨论:

  • 当优先队列元素不足 k 个,可将当前元素直接放入队列中;
  • 当优先队列元素达到 k 个,并且当前元素大于栈顶元素(栈顶元素必然不是答案),可将当前元素放入队列中。

代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->a-b);
        for (int x : nums) {
            if (q.size() < k || q.peek() < x) q.add(x);
            if (q.size() > k) q.poll();
        }
        return q.peek();
    }
}
  • 时间复杂度:
  • 空间复杂度:

快速选择

对于给定数组,求解第 k大元素,且要求线性复杂度,正解为使用「快速选择」做法。

基本思路与「快速排序」一致,每次敲定一个基准值 x,根据当前与 x 的大小关系,将范围在 划分为到两边。

同时利用,利用题目只要求输出第 k 大的值,而不需要对数组进行整体排序,我们只需要根据划分两边后,第 k大数会落在哪一边,来决定对哪边进行递归处理即可。

❝快速排序模板为面试向重点内容,需要重要掌握。 ❞

代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    int[] nums;
    int qselect(int l, int r, int k) {
        if (l == r) return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) swap(i, j);
        }
        if (k <= j) return qselect(l, j, k);
        else return qselect(j + 1, r, k);
    }
    void swap(int i, int j) {
        int c = nums[i];
        nums[i] = nums[j];
        nums[j] = c;
    }
    public int findKthLargest(int[] _nums, int k) {
        nums = _nums;
        int n = nums.length;
        return qselect(0, n - 1, n - k);
    }
}
  • 时间复杂度:期望O(n)
  • 空间复杂度:忽略递归带来的额外空间开销,复杂度为O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.215 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

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

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【面试高频题】难度 2.5/5,多解法经典面试笔试题
这是 LeetCode 上的「786. 第 K 个最小的素数分数」,难度为「中等」。
宫水三叶的刷题日记
2022/10/30
2790
【面试高频题】难度 2.5/5,多解法经典面试笔试题
米哈游(原神)终面算法原题
在房地产行业的上升周期中,房企普遍的高杠杆率和过度扩张如今成为一种"回旋镖",对各个层面都产生了影响。
宫水三叶的刷题日记
2024/02/06
4710
米哈游(原神)终面算法原题
【面试高频题】可拓展变形的「区间求和」经典题
这是 LeetCode 上的「1893. 检查是否区域内所有整数都被覆盖」,难度为「简单」。
宫水三叶的刷题日记
2022/05/25
5000
【每日算法Day 82】面试经典题:求第K大数,我写了11种实现,不来看看吗?
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
godweiyang
2020/04/02
7770
【综合笔试题】难度 3/5,多解法 LIS 问题
这是 LeetCode 上的 「354. 俄罗斯套娃信封问题」 ,难度为 「困难」。
宫水三叶的刷题日记
2021/06/23
6720
【综合笔试题】难度 4/5,综合构造运用题
假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 表示第 个人的身高为 ,前面 正好 有 个身高大于或等于 的人。
宫水三叶的刷题日记
2022/05/25
6250
【综合笔试题】难度 4/5,综合构造运用题
【面试高频题】难度 1.5/5,常见字符串线性 DP 运用题
这是 LeetCode 上的「467. 环绕字符串中唯一的子字符串」,难度为「中等」。
宫水三叶的刷题日记
2022/11/01
3410
【面试高频题】难度 2/5,超常规多语言多解法笔试题
这是 LeetCode 上的 「373. 查找和最小的K对数字」 ,难度为 「中等」。
宫水三叶的刷题日记
2022/11/01
2960
【面试高频题】难度 1/5,简单二叉树寻值问题
这是 LeetCode 上的 「230. 二叉搜索树中第K小的元素」 ,难度为 「中等」。
宫水三叶的刷题日记
2023/02/27
3890
【面试高频题】难度 1.5/5,经典「前缀和 + 二分」运用题
这是我们「刷穿 LeetCode」系列文章的第 No.209 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
宫水三叶的刷题日记
2022/06/21
3270
【面试高频题】难度 1.5/5,二分经典运用题
数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|(0 <= i < n)的 总和(下标从 开始)。
宫水三叶的刷题日记
2022/10/30
3550
【RMQ 专题】关于 RMQ 的若干解法(内含彩蛋)
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
宫水三叶的刷题日记
2022/11/01
7160
【面试高频题】难度 1.5/5,超过一半难度在阅读理解上的 ... 高频面试题?!(含破题)
给你一个整数数组 citations,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
宫水三叶的刷题日记
2023/11/22
1700
【面试高频题】难度 1.5/5,超过一半难度在阅读理解上的 ... 高频面试题?!(含破题)
超超超高频面试题,快来混个脸熟(二)
这套题是某大厂为在校生举办的活动,据说是大厂高频面试原题,我代大家刷一刷,给大家伙混个脸熟
ACM算法日常
2021/09/28
4310
【面试高频系列】Top K 问题的多种解法:冒泡排序 & 快速排序 & 优先队列 ...
这是 LeetCode 上的「703. 数据流中的第 K 大元素」,难度为 「Easy」。
宫水三叶的刷题日记
2021/04/08
8390
【综合笔试题】难度 4.5/5,借该问题来实现一个「可计数」的 Trie
这是 LeetCode 上的「1707. 与数组中元素的最大异或值」,难度为「困难」。
宫水三叶的刷题日记
2021/11/12
2980
【综合笔试题】难度 3.5/5,多解法热门二叉树笔试题
Tag : 「数据结构运用」、「二叉树」、「哈希表」、「排序」、「优先队列(堆)」、「DFS」
宫水三叶的刷题日记
2022/11/01
4810
【综合笔试题】难度 3.5/5,多解法热门二叉树笔试题
【面试高频题】难度 2/5,单调栈经典运用
对答案的贡献即是最终答案,但我们忽略了「当 nums 存在重复元素,且该元素作为子数组最大值时,最远左右端点的边界越过重复元素时,导致重复统计子数组」的问题。
宫水三叶的刷题日记
2023/10/25
3170
【面试高频题】难度 2/5,单调栈经典运用
【综合笔试题】难度 4/5,字符处理的线段树经典运用
这是 LeetCode 上的「2213. 由单个字符重复的最长子字符串」,难度为「困难」。
宫水三叶的刷题日记
2022/11/01
5350
LeetCode精选好题(四)
编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
看、未来
2020/08/25
3650
LeetCode精选好题(四)
推荐阅读
相关推荐
【面试高频题】难度 2.5/5,多解法经典面试笔试题
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验