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

LeetCode 2161.根据给定数字划分数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列,使得以下条件均成立:

所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。
所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。
小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。
更正式的,考虑每一对 pi,pj ,pi 是初始时位置 i 元素的新位置,pj 是初始时位置 j 元素的新位置。对于小于 pivot 的元素,如果 i < j 且 nums[i] < pivot 和 nums[j] < pivot 都成立,那么 pi < pj 也成立。类似的,对于大于 pivot 的元素,如果 i < j 且 nums[i] > pivot 和 nums[j] > pivot 都成立,那么 pi < pj 。
请你返回重新排列 nums 数组后的结果数组。

示例 1:

输入:nums = [9,12,5,10,14,3,10], pivot = 10
输出:[9,5,3,10,10,12,14]
解释:
元素 9 ,5 和 3 小于 pivot ,所以它们在数组的最左边。
元素 12 和 14 大于 pivot ,所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [9, 5, 3] 和 [12, 14] ,它们在结果数组中的相对顺序需要保留。
示例 2:

输入:nums = [-3,4,3,2], pivot = 2
输出:[-3,2,4,3]
解释:
元素 -3 小于 pivot ,所以在数组的最左边。
元素 4 和 3 大于 pivot ,所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [-3] 和 [4, 3] ,它们在结果数组中的相对顺序需要保留。

提示:

1 <= nums.length <= 105
-106 <= nums[i] <= 106
pivot 等于 nums 中的一个元素。

法一:按顺序保存下来小于pivot和大于pivot的数,再拼接:

class Solution {
public:vector<int> pivotArray(vector<int>& nums, int pivot) {vector<int> small;vector<int> big;int pivotNum = 0;for (int num : nums){if (num < pivot){small.push_back(num);}else if (num > pivot){big.push_back(num);}else{++pivotNum;}}for (int i = 0; i < pivotNum; ++i){small.push_back(pivot);}small.insert(small.end(), big.begin(), big.end());return small;}
};

如果nums的长度为n,此算法时间复杂度为O(n),空间复杂度为O(n)。

法二:直接在结果数组中构建答案,先正向遍历nums,把小于pivot的数按顺序放在左边,然后反向遍历nums,把大于pivot的数按顺序放在右边,中间填充pivot即可:

class Solution {
public:vector<int> pivotArray(vector<int>& nums, int pivot) {vector<int> ans(nums.size());int smallIndex = 0;for (int num : nums){if (num < pivot){ans[smallIndex++] = num;}}int bigIndex = nums.size() - 1;for (vector<int>::reverse_iterator it = nums.rbegin(); it != nums.rend(); ++it){if (*it > pivot){ans[bigIndex--] = *it;}}while (smallIndex <= bigIndex){ans[smallIndex++] = pivot;ans[bigIndex--] = pivot;}return ans;}
};

如果nums的长度为n,此算法时间复杂度为O(n),空间复杂度为O(1)。本解法也可以一遍正向遍历,把大于pivot的值在ans的最后从右往左排,最后再reverse一下大于pivot的值即可:

class Solution {
public:vector<int> pivotArray(vector<int>& nums, int pivot) {vector<int> ans(nums.size(), pivot);int smallIndex = 0;int bigIndex = nums.size() - 1;for (int num : nums){if (num < pivot){ans[smallIndex++] = num;}else if (num > pivot){ans[bigIndex--] = num;}}reverse(ans.begin() + bigIndex + 1, ans.end());return ans;}
};

相关文章:

LeetCode 2161.根据给定数字划分数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列&#xff0c;使得以下条件均成立&#xff1a; 所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。 小于 pivot 的元素…...

ip获取+归属地实现

1.背景 现在的社交平台一般都需要展示用户的归属地,这个功能有下面二个主要功能点,接下来我们来介绍下具体实现。 IP 获取 IP 转归属地 2.ip获取 2.1 Http请求 对于controller的请求,我们只需要写个拦截器,将用户的ip设置进上下文即可,非常方便。 @Override public bo…...

Python的错误和异常

文章目录 python的语法错误异常异常处理用户自定义异常定义清理行为预定义的清理行为 python的语法错误 语法错误&#xff08;Syntax Error&#xff09;是指代码不符合Python语言的语法规则。当解释器在执行代码之前对其进行解析时&#xff0c;如果发现代码中有语法错误&#…...

C语言-------指针进阶(2)

1.指针数组 指针数组表较简单&#xff0c;类比整型数组&#xff0c;字符数组&#xff0c;整型数组里面的元素都是整型变量&#xff0c;字符数组里面 的元素是字符类型&#xff0c;那么指针数组就是数组里面的每个元素都是指针类型&#xff0c;例如int*arr[5]就是一个 指针数…...

Spring El表达式官方文档学习

文章目录 推荐一、概述1、什么是SpEL2、SpEL能做什么 二、SpEL表达式使用1、文字表达式2、属性, 数组, List, Map,和 索引&#xff08;1&#xff09;属性操作&#xff08;2&#xff09;数组和List&#xff08;3&#xff09;Map 3、内嵌List4、内嵌Map5、构建数组6、调用类的方法…...

RK3568 android11 调试陀螺仪模块 MPU6500

一&#xff0c;MPU6500功能介绍 1.简介 MPU6500是一款由TDK生产的运动/惯性传感器&#xff0c;属于惯性测量设备&#xff08;IMU&#xff09;的一种。MPU6500集成了3轴加速度计、3轴陀螺仪和一个板载数字运动处理器&#xff08;DMP&#xff09;&#xff0c;能够提供6轴的运动…...

【HTML】HTML基础6.1(表格以及常见属性)

目录 表格介绍 表格标签 表格标签的常见属性 案例 知识点总结 表格介绍 在浏览器中&#xff0c;我们经常见到形如 这样的表格形式&#xff0c;一般来说&#xff0c;表格是为了让数据看起来更加清晰&#xff0c;增强数据的可读性 有的程序员也会用表格进行排版 表格标签 &…...

数字电路三宝:锁存器、寄存器和触发器

在数字电路设计中&#xff0c;很多电子工程师经常会用到锁存器、寄存器和触发器&#xff0c;它们各自承担着不同的功能&#xff0c;但共同为数字电路的稳定性和高效性提供了坚强保障&#xff0c;下面将谈谈这三大元件&#xff0c;希望对小伙伴们有所帮助。 1、锁存器&#xff0…...

VLC相关资源及使用方法

资源 VLC源码&#xff1a; VLC的源码&#xff0c;与VLC Contrib配合使用可以编译相应的库、程序等&#xff0c;如果没有Contrib&#xff0c;可以使用源码下面的contrib文件夹下对应程序自动下载&#xff0c;单独编译&#xff0c;但是速度很慢。 下载地址&#xff1a; 官网&…...

4_相机透镜畸变

理论上讲&#xff0c;是可能定义一种透镜而不引入任何畸变的。然而现实世界没有完美的透镜。这主要是制造上的原因&#xff0c;因为制作一个“球形”透镜比制作一个数学上理想的透镜更容易。而且从机械方面也很难把透镜和成像仪保持平行。下面主要描述两种主要的透镜畸变并为他…...

微信小程序(四十六)登入界面-进阶版

注释很详细&#xff0c;直接上代码 上一篇 此文使用了vant组件库&#xff0c;没有安装配置的可以参考此篇vant组件的安装与配置 新增内容&#xff1a; 1.手机号与验证码格式验证 2.验证码的网络申请和校验 wechat-http模块在好几篇以前已经讲了咋安装的&#xff0c;不记得的友…...

CSP-201712-2-游戏

CSP-201712-2-游戏 解题思路 初始化变量&#xff1a;定义整数变量n和k&#xff0c;分别用来存储小朋友的总数和淘汰的特定数字。然后定义了num&#xff08;用来记录当前报的数&#xff09;和peopleIndex&#xff08;用来记录当前报数的小朋友的索引&#xff09;。 初始化小朋…...

记录SSM项目集成Spring Security 4.X版本 之 加密验证和记住我功能

目录 前言 一、用户登录密码加密认证 二、记住我功能 前言 本次笔记的记录是接SSM项目集成Spring Security 4.X版本 之 加入DWZ,J-UI框架实现登录和主页菜单显示-CSDN博客https://blog.csdn.net/u011529483/article/details/136255768?spm1001.2014.3001.5502 文章之后补…...

[AutoSar]BSW_Com09 CAN driver 模块FULL(BASIC)CAN、FIFO选择

目录 关键词平台说明一、FULL CAN 和Basic CAN 关键词 嵌入式、C语言、autosar、OS、BSW 平台说明 项目ValueOSautosar OSautosar厂商vector &#xff0c;芯片厂商TI 英飞凌编程语言C&#xff0c;C编译器HighTec (GCC)autosar版本4.3.1 >>>>>回到总目录<&…...

WPF真入门教程30--顺风物流单据管理系统

1、教程回顾 到现在为止&#xff0c;真入门系列教程已完成了29刺由浅入深地讲解&#xff0c;当然不可能讲到了WPF的所有技能点&#xff0c;但读者看到了wpf的内部各种功能及之间的联系&#xff0c;在此基础上&#xff0c;提供一个完整有效的综合项目&#xff0c;本项目采用的是…...

Elasticsearch:向量相似度计算 - 可笑的速度

作者&#xff1a;Chris Hegarty 任何向量数据库的核心都是距离函数&#xff0c;它确定两个向量的接近程度。 这些距离函数在索引和搜索期间执行多次。 当合并段或在图表中导航最近邻居时&#xff0c;大部分执行时间都花在比较向量的相似性上。 对这些距离函数进行微观优化是值…...

两数相加的问题

题目是&#xff1a;给两个非空的链表&#xff0c;表示两个非负整数。它们每位数都是按照逆序的方式存储&#xff0c;并且每一个节点只能存储一位数字。现在两个数相加&#xff0c;并且以相同的形式返回一个表示和的链表。 首先回顾一下&#xff0c;什么是链表&#xff1f;链表…...

微信小程序的单位

在小程序开发中&#xff0c;rpx是一种相对长度单位&#xff0c;用于在不同设备上实现自适应布局。它是微信小程序特有的单位&#xff0c;表示屏幕宽度的 1/750。 rpx单位的好处在于可以根据设备的屏幕宽度进行自动换算&#xff0c;使得页面在不同设备上保持一致的显示效果。例…...

软考通过率真的低吗?

软考通过率有多少&#xff1f;高项有必要找培训机构吗&#xff1f; 相对来说软考的通过率的确比其他考试要低&#xff0c;因为它的知识点有点杂&#xff0c;专业知识、政策、计算机系统各个方面的知识都需要去掌握。根据以往的数据来说高项&#xff08;信息系统项目管理师&…...

国际视频编解码标准提案下载地址

H.266 相关提案下载地址&#xff1a;http://phenix.it-sudparis.eu/jvet/ 更新的地址&#xff1a;https://jvet-experts.org/ H.265 提案下载地址&#xff1a;http://phenix.int-evry.fr/jct/ 标准文档下载地址&#xff1a;http://www.itu.int/rec/T-REC-H.265 H.264 提案下载…...

线性化加性模型与子尺度混合:实现概率空间直接可解释的机器学习

1. 项目概述与核心痛点 在金融风控、医疗诊断这些对决策过程要求“看得见、摸得着”的领域&#xff0c;我们这些从业者每天都在和模型的可解释性较劲。你肯定遇到过这种情况&#xff1a;业务方拿着一个逻辑回归模型的风险评分问你&#xff1a;“这个客户的‘历史逾期次数’这个…...

3步解锁Windows远程桌面多人连接:RDP Wrapper Library完整指南

3步解锁Windows远程桌面多人连接&#xff1a;RDP Wrapper Library完整指南 【免费下载链接】rdpwrap RDP Wrapper Library 项目地址: https://gitcode.com/gh_mirrors/rd/rdpwrap 你是否曾因Windows家庭版无法支持多人远程桌面连接而感到困扰&#xff1f;当团队成员需要…...

鸿蒙今日穿搭页面构建:单品清单、一周搭配日历与穿搭提示模块详解

鸿蒙今日穿搭页面构建&#xff1a;单品清单、一周搭配日历与穿搭提示模块详解 前言 在 HarmonyOS 6.0 应用开发中&#xff0c;穿搭类页面的单品管理、周计划安排和温馨提醒是完善用户体验的重要补充模块。本文将以“今日穿搭”应用中的“单品清单”网格模块、“一周搭配日历”周…...

高中化学碳酸盐受热分解,常考易错

一、详细总结 1. 碳酸正盐&#xff08;含 ( \text{CO}_3^{2-} )&#xff09; 碳酸正盐的热稳定性与金属阳离子的极化能力密切相关&#xff0c;大致规律如下&#xff1a;类别代表物热稳定性与分解产物化学方程式&#xff08;条件&#xff1a;加热&#xff09;ⅠA族&#xff08;除…...

DeepSeek技术搜索RAG Pipeline重构实录:从模糊匹配到精准意图识别的6次AB测试数据全公开

更多请点击&#xff1a; https://kaifayun.com 第一章&#xff1a;DeepSeek技术搜索RAG Pipeline重构实录&#xff1a;从模糊匹配到精准意图识别的6次AB测试数据全公开 在DeepSeek内部技术文档搜索系统升级中&#xff0c;我们对原有RAG Pipeline进行了深度重构&#xff0c;核心…...

痛苦本身没有价值,从痛苦中提炼出的原则才有价值

如何打破"好了伤疤忘了疼"的人性循环 目录 如何打破"好了伤疤忘了疼"的人性循环 为什么我们天生就"好了伤疤忘了疼" 真正有效的解决方法:把"感性记忆"转化为"理性制度" 第一级:痛苦发生时——立刻"固化"教训,…...

告别Typora和Vditor?在WordPress后台打造你的全能Markdown写作环境

在WordPress中构建专业级Markdown写作环境的完整指南 对于习惯使用Typora、Vditor等独立Markdown编辑器的创作者来说&#xff0c;WordPress后台的默认编辑器往往显得笨重且功能有限。但通过合理的插件配置和主题选择&#xff0c;我们完全可以在WordPress中打造一个媲美专业编辑…...

跨境社媒运营真正难的 不是内容不够而是账号越来越没有“主线感”

很多团队做跨境社媒时&#xff0c;前期最容易把注意力放在内容数量上。 今天发没发&#xff0c;明天补几条&#xff0c;哪个平台还没铺&#xff0c;哪种形式最近更容易起量。 这些当然重要&#xff0c;因为账号在起步阶段&#xff0c;首先得先“动起来”。但真正做一段时间之后…...

DECA加速器:神经网络模型压缩的硬件优化方案

1. DECA加速器&#xff1a;神经网络模型压缩的硬件突围在AI推理领域&#xff0c;模型压缩技术如同给神经网络"瘦身"——通过量化和稀疏化减少参数规模&#xff0c;但压缩后的数据需要解压才能计算&#xff0c;这个"拆包装"的过程往往成为性能瓶颈。传统CPU…...

YgoMaster终极指南:如何在电脑上免费畅玩游戏王大师决斗

YgoMaster终极指南&#xff1a;如何在电脑上免费畅玩游戏王大师决斗 【免费下载链接】YgoMaster Offline Yu-Gi-Oh! Master Duel 项目地址: https://gitcode.com/gh_mirrors/yg/YgoMaster 你是否渴望随时随地体验《游戏王大师决斗》的精彩对决&#xff0c;却受限于网络连…...