阿里 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…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
