阿里 C++面试,算法题没做出来,,,
我本人是非科班学 C++ 后端和嵌入式的。在我面试的过程中,竟然得到了阿里 C++ 研发工程师的面试机会。因为,阿里主要是用 Java 比较多,C++ 的岗位比较少,所以感觉这个机会还是挺难得的。
阿里 C++ 研发工程师面试考了我一道类似于快速排序算法的算法题,虽然我算法题又一次没做出来然后面试挂了。
题目描述:
题号:215
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

解题思路:
思路一:快排变体(快速选择)
快速选择算法,这是快速排序算法的一种变种。快速选择算法可以在平均情况下以O(n)的时间复杂度找到数组中的第k个最小(或最大)元素。
步骤如下:
-
选择一个基准元素:我们可以随机选择一个元素作为基准,或者选择数组的第一个、最后一个或中间的元素。
-
分区:根据基准元素对数组进行分区,使得所有小于基准的元素都在基准的左边,所有大于基准的元素都在基准的右边。
-
判断基准元素的位置:如果基准元素正好是第k个最大的元素(从0开始计数),则直接返回该元素。如果基准元素的位置大于k,则在基准的左边部分继续寻找;如果基准元素的位置小于k,则在基准的右边部分继续寻找,并调整k的值。
-
递归:在选定的部分中重复上述步骤,直到找到第k个最大的元素。
时间复杂度:O(N)
空间复杂度:O(log N)
C++
// C++
class Solution {
public:int quickselect(vector<int> &nums, int l, int r, int k) {if (l == r)return nums[k];int partition = nums[l], i = l - 1, j = r + 1;while (i < j) {do i++; while (nums[i] < partition);do j--; while (nums[j] > partition);if (i < j)swap(nums[i], nums[j]);}if (k <= j)return quickselect(nums, l, j, k);else return quickselect(nums, j + 1, r, k);}
int findKthLargest(vector<int> &nums, int k) {int n = nums.size();return quickselect(nums, 0, n - 1, n - k);}
};
go
// go
func findKthLargest(nums []int, k int) int {n := len(nums)return quickselect(nums, 0, n - 1, n - k)
}
func quickselect(nums []int, l, r, k int) int{if (l == r){return nums[k]}partition := nums[l]i := l - 1j := r + 1for (i < j) {for i++;nums[i]<partition;i++{}for j--;nums[j]>partition;j--{}if (i < j) {nums[i],nums[j]=nums[j],nums[i]}}if (k <= j){return quickselect(nums, l, j, k)}else{return quickselect(nums, j + 1, r, k)}
}
相关文章:
阿里 C++面试,算法题没做出来,,,
我本人是非科班学 C 后端和嵌入式的。在我面试的过程中,竟然得到了阿里 C 研发工程师的面试机会。因为,阿里主要是用 Java 比较多,C 的岗位比较少,所以感觉这个机会还是挺难得的。 阿里 C 研发工程师面试考了我一道类似于快速…...
【自动驾驶汽车通讯协议】GMSL通信技术以及加串器(Serializer)解串器(Deserializer)介绍
文章目录 0. 前言1. GMSL技术概述2. 为什么需要SerDes?3. GMSL技术特点4.自动驾驶汽车中的应用5. 结论 0. 前言 按照国际惯例,首先声明:本文只是我自己学习的理解,虽然参考了他人的宝贵见解及成果,但是内容可能存在不准…...
Uiautomator2与weditor配置一直报错咋办
作者在配置这两个的时候绞尽脑汁了,u2的init总是报错并且无法自动在手机上安装atx,weditor可以打开但是只要对元素操作或者任意操作就会让你去重新init,搞得作者焦头烂额,而且网上各种各样的报错信息眼花缭乱,作者几乎…...
Java后端面试题:MySQL篇
目录 MySQL基础部分 1. SELECT语句完整的执行顺序是什么? 2. 说一说内连接和外连接。 3. 请说说数据库三大范式。 4. 请你说说视图的作用,视图可以更改么? 架构 5. 请你说一说MySQL架构。 6. 请你说说一条SQL语句的执行过程ÿ…...
# Excel 操作大全
Excel 操作大全 文章目录 Excel 操作大全单元格文本换行计算SUM 单元格 文本换行 设置自动换行,在文本前面使用 AltEnter键即可换行文本前面可以输入空格实现段前缩进的效果 计算SUM 求和函数...
javascript中快速获取最大值和最小值
在 ES6 中,你可以使用 Math.max 和 Math.min 函数来获取一组数字中的最大值和最小值。这两个函数都接受一个可变数量的参数,并返回这些参数中的最大值或最小值。 以下是一个示例: const numbers [1, 2, 3, 4, 5];const max Math.max(...n…...
git merge啥意思
git merge 是 Git 中的一个命令,用于将一个分支的更改合并到另一个分支中。当你在一个项目中有多个开发人员同时工作,或者你在不同的特性分支上开发新功能时,git merge 命令就非常有用。它可以帮助你将不同分支上的更改整合在一起。 git mer…...
Web编程---Servlet技术
文章目录 一、目的二、原理三、过程1. TestServlet02文件演示效果2. TestServlet03文件演示效果3. TestServlet04与TestServlet05文件演示效果4. 控制台展示生命周期过程 四、代码web.xml文件TestServlet02.java文件TestServlet03.java文件TestServlet04.java文件TestServlet05…...
【cocos creator】输入框滑动条联动小组建
滑动条滑动输入框内容会改变 输入框输入,滑动条位置改变 const { ccclass, property } cc._decorator;ccclass() export default class SliderEnter extends cc.Component {property({ type: cc.Float, displayName: "最大值", tooltip: "" }…...
Flink时间窗口程序骨架结构
前言 Flink 作业的基本骨架结构包含三部分:创建执行环境、定义数据处理逻辑、提交并执行Flink作业。 日常大部分 Flink 作业是基于时间窗口计算模型的,同样的,开发一个Flink时间窗口作业也有一套基本的骨架结构,了解这套结构有助…...
计算机视觉之可做什么
1、计算机视觉的应用 计算机视觉在我们生活中已经有了很广泛的应用,在我们可见、不可见;可感知、不可感知的地方,深深地影响了我们的生活、生产方式。 日常生活:美颜相机、火车站刷脸进站、线上办理业务的身份认证、自动驾驶等等…...
观察者模式的思考
观察者模式由来 观察者模式(Observer Pattern)是一种行为型设计模式,它的起源可以追溯到20世纪90年代初,由设计模式四人帮(Erich Gamma, Richard Helm, Ralph Johnson 和 John Vlissides)在其著作《设计模…...
ORACLE SELECT INTO 赋值为空,抛出 NO DATA FOUND 异常
例子: DECLARE ORDER_NUM VARCHAR2(20); BEGIN SELECT S.ORDER_NUM INTO ORDER_NUM FROM SALES_ORDER S WHERE S.ID122344; DBMS_OUTPUT.PUT_LINE(单号: || ORDER_NUM); END; 在查询结果为空的情况下,以上代码会报错:未找到任何数据 解决方…...
GPT提示词
参考 提示词大全: GPT提示词大全(中英文双语)持续更新 提示词.com...
Redis协议详解及其异步应用
目录 一、Redis Pipeline(管道)概述优点使用场景工作原理Pipeline 的基本操作步骤C 示例(使用 [hiredis](https://github.com/redis/hiredis) 库) 二、Redis 事务概述事务的前提事务特征(ACID 分析)WATCH 命…...
LeetCode213:打家劫舍II
题目链接:213. 打家劫舍 II - 力扣(LeetCode) 代码如下 class Solution { public:int rob(vector<int>& nums) {if(nums.size() 0) return 0;if(nums.size() 1) return nums[0];if(nums.size() 2) return max(nums[0…...
linux一二三章那些是重点呢
第一章 静态库动态库的区别 什么是库 库文件是计算机上的一类文件,可以简单的把库文件看成一种代码仓库,它提供给使用者一些可以直接 拿来用的变量、函数或类。 如何制作 静态动态库 静态库: GCC 进行链接时,会把静态库中代码打…...
C语言中的程序入口:超越main函数的探索
在C语言中,尽管main函数是标准程序的默认入口点,但借助编译器特性和链接器选项,我们可以指定其他函数作为程序的入口。GCC编译器通过-e选项,允许我们将任何符合签名的函数作为程序的入口。这一特性可以用于特定的实验需求、特定系…...
《面试之MQ篇》
《面试之MQ篇》 1. 为什么要使用MQ 首先,面试官问的第一个问题或者说是逼问的一个问题:“为什么要使用MQ”其实面试官问这个问题就是想考察你MQ的特性,这个时候呢,我们必须要答出三点:解耦、异步、削峰。 1. 解耦 1. 传统系统…...
Git 分支操作-开发规范
一、背景 在实际开发中,一般在主分支的基础上单独创建一个新的分支进行开发,最后合并到master分支,而不是直接在master分支进行开发。 二、新建分支 1、初始状态,local为本地分支,remote为远程分支 2、单击 “Remot…...
告别“替身攻击”:手把手教你用零阶优化(ZOO)直接黑盒攻击DNN模型
零阶优化实战:无需替代模型的黑盒对抗攻击指南 当面对一个部署在云端的深度学习API时,传统白盒攻击手段往往束手无策——既无法获取模型架构,也不能执行反向传播。本文将揭示如何运用零阶优化技术,仅通过输入输出查询就能构造高效…...
5分钟搞定!Fun-ASR-MLT-Nano-2512多语言语音识别一键部署指南
5分钟搞定!Fun-ASR-MLT-Nano-2512多语言语音识别一键部署指南 1. 快速了解Fun-ASR-MLT-Nano-2512 Fun-ASR-MLT-Nano-2512是阿里通义实验室推出的轻量级多语言语音识别模型,特别适合需要本地化部署的场景。这个800M参数的模型虽然小巧,但功能…...
OpenClaw版本升级:nanobot镜像迁移全记录
OpenClaw版本升级:nanobot镜像迁移全记录 1. 升级背景与准备工作 去年我在本地部署了基于OpenClaw v1.2的nanobot镜像,这套系统一直稳定运行着我的自动化办公流程。直到上个月收到社区通知,新版本v2.1重构了核心架构,特别是技能…...
计算机网络 之 【自定义协议、序列化与反序列化】(C++使用JSON示例)
目录 1.自定义协议与序列化/反序列化 2.Json简介 Json是什么 第三方库提供,使用时包含头文件 JSON 的数据类型 JSON结构示例 C使用JSON示例 1.自定义协议与序列化/反序列化 协议的必要性 协议是通信双方的约定,它定义了数据的格式和含义ÿ…...
5分钟掌握游戏高清截图秘诀:SRWE窗口分辨率自定义完整教程
5分钟掌握游戏高清截图秘诀:SRWE窗口分辨率自定义完整教程 【免费下载链接】SRWE Simple Runtime Window Editor 项目地址: https://gitcode.com/gh_mirrors/sr/SRWE 你是否曾梦想为心爱的游戏角色拍摄一张高清壁纸,却发现游戏分辨率选项有限&…...
Scarab:空洞骑士模组管理效率提升83%的智能工具
Scarab:空洞骑士模组管理效率提升83%的智能工具 【免费下载链接】Scarab An installer for Hollow Knight mods written in Avalonia. 项目地址: https://gitcode.com/gh_mirrors/sc/Scarab 如何解决模组管理难题?3大创新让你告别手动配置烦恼 对…...
从国科大NLP课程笔记出发:手把手教你用Python复现CYK句法分析算法
从理论到实践:用Python实现CYK句法分析算法的完整指南 在自然语言处理领域,句法分析是理解句子结构的关键步骤。CYK算法作为一种经典的句法分析技术,因其简洁高效的特点,成为许多NLP工程师工具箱中的必备武器。本文将带你从零开始…...
STC-50kg
【广州兰瑟★电子-杨工】提供的STC-50kg 是美国威世世铨(Vishay Celtron)旗下一款经典的 S 型拉压双向称重 / 测力传感器,量程 50 公斤 (50kgf / 490N)。 一、核心参数(标准型) 量程:50 kg (拉力 / 压力双向…...
Python多线程性能翻倍实录(GIL禁用+细粒度原子操作配置全指南)
第一章:Python无锁GIL环境下的并发模型概览Python 的全局解释器锁(GIL)长期被视为多线程 CPU 密集型任务的瓶颈。然而,随着 CPython 3.13 的正式引入“实验性无锁 GIL”(--without-pymalloc 配合 --with-gildisabled 构…...
vLLM 5.0.4 实战:从参数解析到批量推理的性能调优指南
1. vLLM 5.0.4核心参数解析与实战配置 初次接触vLLM时,最让人头疼的就是那一长串参数列表。我在实际项目中使用Meta-Llama-3.1-8B-Instruct模型时,就曾因为参数配置不当导致显存爆炸。下面分享几个关键参数的实战经验: LLM类参数中的max_mode…...
