米哈游(原神)终面算法原题
恒大正式破产
准确来说,是中国恒大(恒大汽车、恒大物业已于 2024-01-30 复牌)。
恒大破产,注定成为历史的注目焦点。
作为首个宣布破产的房地产企业,恒大的破产规模也创历史新高。
房地产作为曾推动中国三分之一经济增长的行业,恒大是当中毫无疑问的佼佼者。
能够成就这样的巨无霸,自然是有时代和政策因素的。
在房地产行业的上升周期中,房企普遍的高杠杆率和过度扩张如今成为一种"回旋镖",对各个层面都产生了影响。
即使你和我一样,家里没有几套房,没有买恒大的LW楼,也没有持有恒大系股票,但我们都感受到了这波的消费低迷和各行业的裁员潮,这与房地产去泡沫化不无关系。
中国楼市基本对标美国股市,当一个国家的重要经济载体出现问题(失去信心),普通人不可能独善其身。
当然了,最幸福的人不会变。
仍然是那些无论房地产高歌猛进还是岌岌可危,都自诩与他无关的人(他觉得自己不考虑买房嘛,能有啥关系)。
我相信这批人,和看到《游戏意见稿》就只讨论「该不该给氪金游戏充值」是同一批人。
随他们去吧。
...
回归主线。
自上次写了米哈游的一面原题和变形题之后,又有读者来投稿了。
据说,这次是米哈游(原神)终面算法题。
看着确实像,因为这是一道适合「由浅入深」的题目,适合在面试过程中有来有回。
启动!
题目描述
平台:LeetCode
题号:215
给定整数数组 nums
和整数 k
,请返回数组中第 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
提示:
值域映射 + 树状数组 + 二分
除了直接对数组进行排序,取第 位的 做法以外。
对于值域大小 小于 数组长度本身时,我们还能使用「树状数组 + 二分」的 做法,其中 为值域大小。
首先值域大小为 ,为了方便,我们为每个 增加大小为 的偏移量,将值域映射到 的空间。
将每个增加偏移量后的 存入树状数组,考虑在 范围内进行二分,假设我们真实第 大的值为 ,那么在以 为分割点的数轴上,具有二段性质:
-
在 范围内的数 满足「树状数组中大于等于 的数不低于 个」 -
在 范围内的数 不满足「树状数组中大于等于 的数不低于 个」
二分出结果后再减去刚开始添加的偏移量即是答案。
Java 代码:
class Solution {
int M = 100010, 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;
}
}
C++ 代码:
class Solution {
public:
int N = 200010, M = 100010, tr[200010];
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]++;
}
int findKthLargest(vector<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;
}
};
Python 代码:
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
N, M = 200010, 100010
tr = [0] * N
def lowbit(x):
return x & -x
def query(x):
ans = 0
i = x
while i > 0:
ans += tr[i]
i -= lowbit(i)
return ans
def add(x):
i = x
while i < N:
tr[i] += 1
i += lowbit(i)
for x in nums:
add(x + M)
l, r = 0, N - 1
while l < r:
mid = l + r + 1 >> 1
if query(N - 1) - query(mid - 1) >= k: l = mid
else: r = mid - 1
return r - M
TypeScript 代码:
function findKthLargest(nums: number[], k: number): number {
const N = 200010, M = 100010;
const tr = new Array(N).fill(0);
const lowbit = function(x: number): number {
return x & -x;
};
const add = function(x: number): void {
for (let i = x; i < N; i += lowbit(i)) tr[i]++;
};
const query = function(x: number): number {
let ans = 0;
for (let i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;
};
for (const x of nums) add(x + M);
let l = 0, r = N - 1;
while (l < r) {
const mid = l + r + 1 >> 1;
if (query(N - 1) - query(mid - 1) >= k) l = mid;
else r = mid - 1;
}
return r - M;
};
-
时间复杂度:将所有数字放入树状数组复杂度为 ;二分出答案复杂度为 ,其中 为值域大小。整体复杂度为 -
空间复杂度:
优先队列(堆)
另外一个容易想到的想法是利用优先队列(堆),由于题目要我们求的是第 大的元素,因此我们建立一个小根堆。
根据当前队列元素个数或当前元素与栈顶元素的大小关系进行分情况讨论:
-
当优先队列元素不足 个,可将当前元素直接放入队列中; -
当优先队列元素达到 个,并且当前元素大于栈顶元素(栈顶元素必然不是答案),可将当前元素放入队列中。
Java 代码:
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();
}
}
C++ 代码:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> q;
for (int x : nums) {
if (q.size() < k || q.top() < x) q.push(x);
if (q.size() > k) q.pop();
}
return q.top();
}
};
Python 代码:
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
q = []
for x in nums:
if len(q) < k or q[0] < x:
heapq.heappush(q, x)
if len(q) > k:
heapq.heappop(q)
return q[0]
-
时间复杂度: -
空间复杂度:
快速选择
对于给定数组,求解第 大元素,且要求线性复杂度,正解为使用「快速选择」做法。
基本思路与「快速排序」一致,每次敲定一个基准值 x
,根据当前与 x
的大小关系,将范围在 的 划分为到两边。
同时利用,利用题目只要求输出第 大的值,而不需要对数组进行整体排序,我们只需要根据划分两边后,第 大数会落在哪一边,来决定对哪边进行递归处理即可。
❝快速排序模板为面试向重点内容,需要重要掌握。
❞
Java 代码:
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);
}
}
C++ 代码:
class Solution {
public:
vector<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(nums[i], nums[j]);
}
if (k <= j) return qselect(l, j, k);
else return qselect(j + 1, r, k);
}
int findKthLargest(vector<int>& _nums, int k) {
nums = _nums;
int n = nums.size();
return qselect(0, n - 1, n - k);
}
};
Python 代码:
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def qselect(l, r, k):
if l == r:
return nums[k]
x, i, j = nums[l], l - 1, r + 1
while i < j:
i += 1
while nums[i] < x:
i += 1
j -= 1
while nums[j] > x:
j -= 1
if i < j:
nums[i], nums[j] = nums[j], nums[i]
if k <= j:
return qselect(l, j, k)
else:
return qselect(j + 1, r, k)
n = len(nums)
return qselect(0, n - 1, n - k)
TypeScript 代码:
function findKthLargest(nums: number[], k: number): number {
const qselect = function(l: number, r: number, k: number): number {
if (l === r) return nums[k];
const x = nums[l];
let i = l - 1, j = r + 1;
while (i < j) {
i++;
while (nums[i] < x) i++;
j--;
while (nums[j] > x) j--;
if (i < j) [nums[i], nums[j]] = [nums[j], nums[i]];
}
if (k <= j) return qselect(l, j, k);
else return qselect(j + 1, r, k);
};
const n = nums.length;
return qselect(0, n - 1, n - k);
};
-
时间复杂度:期望 -
空间复杂度:忽略递归带来的额外空间开销,复杂度为
我是宫水三叶,每天都会分享算法题解,并和大家聊聊近期的所见所闻。
欢迎关注,明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台发布
相关文章:
米哈游(原神)终面算法原题
恒大正式破产 准确来说,是中国恒大(恒大汽车、恒大物业已于 2024-01-30 复牌)。 恒大破产,注定成为历史的注目焦点。 作为首个宣布破产的房地产企业,恒大的破产规模也创历史新高。 房地产作为曾推动中国三分之一经济增…...
机器学习如何改变缺陷检测的格局?
机器学习在缺陷检测中扮演着重要的角色,它能够通过自动学习和识别各种缺陷的模式和特征,改变缺陷检测的格局。以下是机器学习在缺陷检测中的一些应用和优势: 自动化检测:机器学习技术可以自动化处理大量的数据,通过学…...
【Java万花筒】图数据库 vs 多模型数据库:哪种数据库适合你的应用场景?
解密图数据库与多模型数据库:特性、查询语言和成功案例的全景展示 前言 图数据库和多模型数据库在当今数据处理领域扮演着重要的角色。本文将介绍四个主要的图数据库和多模型数据库:Neo4j、Apache TinkerPop、JGraphT和ArangoDB,探索它们的…...

【射影几何13 】梅氏定理和塞瓦定理探讨
梅氏定理和塞瓦定理 目录 一、说明二、梅涅劳斯(Menelaus)定理三、塞瓦(Giovanni Ceva)定理四、塞瓦点的推广 一、说明 在射影几何中,梅涅劳斯(Menelaus)定理和塞瓦定理是非常重要的基本定理。通过这两个定…...

Powershell Install 一键部署Openssl+certificate证书创建
前言 Openssl 是一个方便的实用程序,用于创建自签名证书。您可以在所有操作系统(如 Windows、MAC 和 Linux 版本)上使用 OpenSSL。 Windows openssl 下载 前提条件 开启wmi,配置网卡,参考 自签名证书 创建我们自己的根 CA 证书和 CA 私钥(我们自己充当 CA)创建服务器…...

SERVLET线程模型
1. SERVLET线程模型 Servlet规范定义了两种线程模型来阐明Web容器应该如何在多线程环境中处理servlet。第一种模型称为多线程模型,默认在此模型内执行所有servlet。在此模型中,每次客户机向servlet发送请求时Web容器都启动一个新线程。这意味着可能有多个线程同时访问servle…...

【开源】基于JAVA+Vue+SpringBoot的新能源电池回收系统
目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 用户档案模块2.2 电池品类模块2.3 回收机构模块2.4 电池订单模块2.5 客服咨询模块 三、系统设计3.1 用例设计3.2 业务流程设计3.3 E-R 图设计 四、系统展示五、核心代码5.1 增改电池类型5.2 查询电池品类5.3 查询电池回…...

【蓝桥杯冲冲冲】Prime Gift
【蓝桥杯冲冲冲】Prime Gift 蓝桥杯备赛 | 洛谷做题打卡day31 文章目录 蓝桥杯备赛 | 洛谷做题打卡day31Prime Gift题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示题解代码我的一些话 Prime Gift 题面翻译 给你 n n n 个…...

【PyQt】06-.ui文件转.py文件
文章目录 前言方法一、基本脚本查看自己的uic安装目录 方法二、添加到扩展工具里面(失败了)方法二的成功步骤总结 前言 方法一、基本脚本 将Qt Designer(一种图形用户界面设计工具)生成的.ui文件转换为Python代码的脚本。 pytho…...
λ-矩阵知识点
原文:链接 λ-矩阵 若矩阵 A \mathbf{A} A 的元素为关于 λ λ λ 的多项式,则称 A \mathbf{A} A 为 λ λ λ-矩阵 (表示为 A ( λ ) \mathbf{A}(λ) A(λ)). λ λ λ-矩阵也存在秩、逆、初等变换、相抵的概念, 但是有一些不同. 定义. λ λ λ-矩阵的秩是…...

cocos creator 3.x 预制体无法显示
双击预制体,进入详情页,没有显示资源 Bomb 是个预制体,但是当我双击进来什么都没有了,无法对预制体进行可视化编辑 目前我只试出来一个解决方法: 把预制体拖进Canvas文件中,这样就能展示到屏幕上ÿ…...

Tomcat之虚拟主机
1.创建存放网页的目录 mkdir -p /web/{a,b} 2.添加jsp文件 vi /web/a/index.jsp <% page language"java" import"java.util.*" pageEncoding"UTF-8"%> <html> <head><title>JSP a page</title> </head> …...

前后端数据校验
前端校验内容 前端开发中的必要校验,可以保证用户输入的数据的准确性、合法性和安全性。同时,这些校验也有助于提供良好的用户体验和防止不必要的错误提交到后端。 1、必填字段校验: 对于必填的字段,需确保用户输入了有效的数据…...
Python把png图片转成jpg图片
在Python中,您可以使用PIL(Python Imaging Library,也被称为Pillow)库来将PNG图片转换为JPG格式。以下是一个简单的示例: 首先,确保你已经安装了Pillow库。如果没有安装,可以使用pip来安装&…...

STM32搭建开发环境
常用开发工具简介 集成开发环境 MDK:全名RealViewMDK,是Keil公司(已被ARM收购的)一款集成开发环境,界面美观,简单易用,是STM32最常用的集成开发环境EWARM:IAR公司的一款集成开发环…...

C#入门详解_01_课程简介、C#语言简介、开发环境和学习资料的准备
文章目录 1. 课程简介2. C#语言简介3.开发环境与学习资料 1. 课程简介 开设本课程的目的 传播C#开发的知识,让更多的人有机会接触到软件开发行业引导有兴趣或者想转行的朋友进入软件开发行业 课程内容 完整讲述C#语言在实际软件开发中的应用采用知识讲述加实例程序…...
C++服务器端开发(2):确定服务器框架
选择C服务器框架时,可以考虑: 并发性能:C的强项之一是其并发性能。选择一个具有高并发处理能力的服务器框架,可以更好地满足大量并发请求的需求。例如,libevent、Boost.Asio和CppServer都是具有良好并发性能的C服务器框…...
CGAL::2D Arrangements-5
5.Arrangement无界曲线 前几章中构建和操作的所有Arrangement都只由线段引起,线段尤其是有界曲线。这样的Arrangement总是具有一个包含所有其他Arrangement特征的unbounded face。在本节中,我们将解释如何构造无界曲线的Arrangement。为了简化说明&…...

登录+JS逆向进阶【过咪咕登录】(附带源码)
JS渗透之咪咕登录 每篇前言:咪咕登录参数对比 captcha参数enpassword参数搜索enpassword参数搜索J_RsaPsd参数setPublic函数encrypt加密函数运行时可能会遇到的问题此部分改写的最终形态JS代码:运行结果python编写脚本运行此JS代码:运行结果&…...

CTF秀 ctfshow WEB入门 web1-10 wp精讲
目录 web1_查看源码 web3_抓包 web4-9_目录文件 web10_cookie web1_查看源码 ctrlu 查看源码 web3_抓包 查看源码,无果 抓包,找到flag web4-9_目录文件 GitHub - maurosoria/dirsearch: Web path scanner 下载dirsearch工具扫一下就都出来了 web4-…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...

android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

Linux操作系统共享Windows操作系统的文件
目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项,设置文件夹共享为总是启用,点击添加,可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download(这是我共享的文件夹)&…...
嵌入式面试常问问题
以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...
GeoServer发布PostgreSQL图层后WFS查询无主键字段
在使用 GeoServer(版本 2.22.2) 发布 PostgreSQL(PostGIS)中的表为地图服务时,常常会遇到一个小问题: WFS 查询中,主键字段(如 id)莫名其妙地消失了! 即使你在…...