当前位置: 首页 > news >正文

阿里 C++面试,算法题没做出来,,,

我本人是非科班学 C++ 后端和嵌入式的。在我面试的过程中,竟然得到了阿里​ C++ 研发工程师的面试机会。因为,阿里主要是用 Java 比较多,C++ 的岗位比较少​,所以感觉这个机会还是挺难得的。

阿里 C++ 研发工程师面试考了我一道类似于快速排序算法的算法题,虽然我算法题又一次没做出来然后面试挂了。

题目描述:

题号:215

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

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

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

解题思路:

思路一:快排变体(快速选择)

快速选择算法,这是快速排序算法的一种变种。快速选择算法可以在平均情况下以O(n)的时间复杂度找到数组中的第k个最小(或最大)元素。

步骤如下:

  1. 选择一个基准元素:我们可以随机选择一个元素作为基准,或者选择数组的第一个、最后一个或中间的元素。

  2. 分区:根据基准元素对数组进行分区,使得所有小于基准的元素都在基准的左边,所有大于基准的元素都在基准的右边。

  3. 判断基准元素的位置:如果基准元素正好是第k个最大的元素(从0开始计数),则直接返回该元素。如果基准元素的位置大于k,则在基准的左边部分继续寻找;如果基准元素的位置小于k,则在基准的右边部分继续寻找,并调整k的值。

  4. 递归:在选定的部分中重复上述步骤,直到找到第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 后端和嵌入式的。在我面试的过程中&#xff0c;竟然得到了阿里​ C 研发工程师的面试机会。因为&#xff0c;阿里主要是用 Java 比较多&#xff0c;C 的岗位比较少​&#xff0c;所以感觉这个机会还是挺难得的。 阿里 C 研发工程师面试考了我一道类似于快速…...

【自动驾驶汽车通讯协议】GMSL通信技术以及加串器(Serializer)解串器(Deserializer)介绍

文章目录 0. 前言1. GMSL技术概述2. 为什么需要SerDes&#xff1f;3. GMSL技术特点4.自动驾驶汽车中的应用5. 结论 0. 前言 按照国际惯例&#xff0c;首先声明&#xff1a;本文只是我自己学习的理解&#xff0c;虽然参考了他人的宝贵见解及成果&#xff0c;但是内容可能存在不准…...

Uiautomator2与weditor配置一直报错咋办

作者在配置这两个的时候绞尽脑汁了&#xff0c;u2的init总是报错并且无法自动在手机上安装atx&#xff0c;weditor可以打开但是只要对元素操作或者任意操作就会让你去重新init&#xff0c;搞得作者焦头烂额&#xff0c;而且网上各种各样的报错信息眼花缭乱&#xff0c;作者几乎…...

Java后端面试题:MySQL篇

目录 MySQL基础部分 1. SELECT语句完整的执行顺序是什么&#xff1f; 2. 说一说内连接和外连接。 3. 请说说数据库三大范式。 4. 请你说说视图的作用&#xff0c;视图可以更改么&#xff1f; 架构 5. 请你说一说MySQL架构。 6. 请你说说一条SQL语句的执行过程&#xff…...

# Excel 操作大全

Excel 操作大全 文章目录 Excel 操作大全单元格文本换行计算SUM 单元格 文本换行 设置自动换行&#xff0c;在文本前面使用 AltEnter键即可换行文本前面可以输入空格实现段前缩进的效果 计算SUM 求和函数...

javascript中快速获取最大值和最小值

在 ES6 中&#xff0c;你可以使用 Math.max 和 Math.min 函数来获取一组数字中的最大值和最小值。这两个函数都接受一个可变数量的参数&#xff0c;并返回这些参数中的最大值或最小值。 以下是一个示例&#xff1a; const numbers [1, 2, 3, 4, 5];const max Math.max(...n…...

git merge啥意思

git merge 是 Git 中的一个命令&#xff0c;用于将一个分支的更改合并到另一个分支中。当你在一个项目中有多个开发人员同时工作&#xff0c;或者你在不同的特性分支上开发新功能时&#xff0c;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】输入框滑动条联动小组建

滑动条滑动输入框内容会改变 输入框输入&#xff0c;滑动条位置改变 const { ccclass, property } cc._decorator;ccclass() export default class SliderEnter extends cc.Component {property({ type: cc.Float, displayName: "最大值", tooltip: "" }…...

Flink时间窗口程序骨架结构

前言 Flink 作业的基本骨架结构包含三部分&#xff1a;创建执行环境、定义数据处理逻辑、提交并执行Flink作业。 日常大部分 Flink 作业是基于时间窗口计算模型的&#xff0c;同样的&#xff0c;开发一个Flink时间窗口作业也有一套基本的骨架结构&#xff0c;了解这套结构有助…...

计算机视觉之可做什么

1、计算机视觉的应用 计算机视觉在我们生活中已经有了很广泛的应用&#xff0c;在我们可见、不可见&#xff1b;可感知、不可感知的地方&#xff0c;深深地影响了我们的生活、生产方式。 日常生活&#xff1a;美颜相机、火车站刷脸进站、线上办理业务的身份认证、自动驾驶等等…...

观察者模式的思考

观察者模式由来 观察者模式&#xff08;Observer Pattern&#xff09;是一种行为型设计模式&#xff0c;它的起源可以追溯到20世纪90年代初&#xff0c;由设计模式四人帮&#xff08;Erich Gamma, Richard Helm, Ralph Johnson 和 John Vlissides&#xff09;在其著作《设计模…...

ORACLE SELECT INTO 赋值为空,抛出 NO DATA FOUND 异常

例子&#xff1a; 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; 在查询结果为空的情况下&#xff0c;以上代码会报错&#xff1a;未找到任何数据 解决方…...

GPT提示词

参考 提示词大全&#xff1a; GPT提示词大全&#xff08;中英文双语&#xff09;持续更新 提示词.com...

Redis协议详解及其异步应用

目录 一、Redis Pipeline&#xff08;管道&#xff09;概述优点使用场景工作原理Pipeline 的基本操作步骤C 示例&#xff08;使用 [hiredis](https://github.com/redis/hiredis) 库&#xff09; 二、Redis 事务概述事务的前提事务特征&#xff08;ACID 分析&#xff09;WATCH 命…...

LeetCode213:打家劫舍II

题目链接&#xff1a;213. 打家劫舍 II - 力扣&#xff08;LeetCode&#xff09; 代码如下 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一二三章那些是重点呢

第一章 静态库动态库的区别 什么是库 库文件是计算机上的一类文件&#xff0c;可以简单的把库文件看成一种代码仓库&#xff0c;它提供给使用者一些可以直接 拿来用的变量、函数或类。 如何制作 静态动态库 静态库&#xff1a; GCC 进行链接时&#xff0c;会把静态库中代码打…...

C语言中的程序入口:超越main函数的探索

在C语言中&#xff0c;尽管main函数是标准程序的默认入口点&#xff0c;但借助编译器特性和链接器选项&#xff0c;我们可以指定其他函数作为程序的入口。GCC编译器通过-e选项&#xff0c;允许我们将任何符合签名的函数作为程序的入口。这一特性可以用于特定的实验需求、特定系…...

《面试之MQ篇》

《面试之MQ篇》 1. 为什么要使用MQ 首先,面试官问的第一个问题或者说是逼问的一个问题&#xff1a;“为什么要使用MQ”其实面试官问这个问题就是想考察你MQ的特性&#xff0c;这个时候呢&#xff0c;我们必须要答出三点&#xff1a;解耦、异步、削峰。 1. 解耦 1. 传统系统…...

Git 分支操作-开发规范

一、背景 在实际开发中&#xff0c;一般在主分支的基础上单独创建一个新的分支进行开发&#xff0c;最后合并到master分支&#xff0c;而不是直接在master分支进行开发。 二、新建分支 1、初始状态&#xff0c;local为本地分支&#xff0c;remote为远程分支 2、单击 “Remot…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...