力扣刷题之2576.求出最多标记下标
题干描述
给你一个下标从 0 开始的整数数组 nums
。
一开始,所有下标都没有被标记。你可以执行以下操作任意次:
- 选择两个 互不相同且未标记 的下标
i
和j
,满足2 * nums[i] <= nums[j]
,标记下标i
和j
。
请你执行上述操作任意次,返回 nums
中最多可以标记的下标数目。
示例 1:
输入:nums = [3,5,2,4] 输出:2 解释:第一次操作中,选择 i = 2 和 j = 1 ,操作可以执行的原因是 2 * nums[2] <= nums[1] ,标记下标 2 和 1 。 没有其他更多可执行的操作,所以答案为 2 。
示例 2:
输入:nums = [9,2,5,4] 输出:4 解释:第一次操作中,选择 i = 3 和 j = 0 ,操作可以执行的原因是 2 * nums[3] <= nums[0] ,标记下标 3 和 0 。 第二次操作中,选择 i = 1 和 j = 2 ,操作可以执行的原因是 2 * nums[1] <= nums[2] ,标记下标 1 和 2 。 没有其他更多可执行的操作,所以答案为 4 。
示例 3:
输入:nums = [7,6,8] 输出:0 解释:没有任何可以执行的操作,所以答案为 0 。
题干分析
题目理解
题目给定一个整数数组nums,要求找出数组中最多可以标记的下标数目。操作条件是每次可以选择两个未标记的下标i和j,满足2 * nums[i] <= nums[j],然后标记着两个下标。目标是执行尽可能多的标记操作。
该题目的本质是要求我们找出符合条件的最多配对数,且配对的条件是2 * nums[i] <= nums[j],即选择较小的nums[i]和较大的nums[j]进行配对。
解题思路
1.排序数组
- 为了便于处理每一对下标i和j,我们可以将数组nums按照肾虚排序。排序后的数组让我们能够更加轻松地选择较小的值nums[i]和较大的值nums[i],并比较是否满足条2 * nums[i] <= nums[j]。
- 排序的时间复杂度为O(n log n)。
2.双指针法
排序后,可以使用双指针来处理配对问题。一个指针i从数组的前半部分开始,表示较小值的位置;另一个指针j从数组的后半部分开始,表示较大值的位置。
初始化指针
- 指针i:从0开始,遍历前一半较小的元素
- 指针j:从数组中间numsSize / 2喀什,遍历后一半较大的元素。
配对指针
- 如果满足条件2 * nums[i] <= nums[j],我们可以标记着两个小标,然后移动两个指针,i指向下一个较小值,j指向下一个较大值。
- 如果不满足条件,则移动j指向下一个更大的值,直到找到可以与i配对的值。
3.计数
- 每次找到一个符合条件的配对时,我们将计数器count增加2,表示标记了两个下标。
- 最后返回count即为最多可以标记的下标数目。
详细步骤
1.排序数组
- 将数组nums进行升序排序,这样尅可以更容易找到较小值nums[i]和较大值nums[j].
- 例如,输入nums = [9, 2, 5, 4],排序后的数组为[2,4,5,9]。
2.初始化双指针
- i:指向数组较小的部分,初始值为0。
- j:指向数组较大的部分,初始值为numsSize / 2(数组中间的位置)。
- 例如对于数组[2,4,5,9],i从0开始,j从2开始。
3.使用双指针遍历数组并配对
- 判断2 * nums[i] <= nums[j]是否成立。
- 如果成立,则标记这两个下标,移动i和j。
- 如果不成立,则只移动j,继续寻找更大的值。
4.计数并返回
- 每找到一对符合条件的下标,计数器增加2,最后返回计数器的值。
#include <stdio.h>
#include <stdlib.h>//比较函数,用于qsort排序
int cmp(const void* a, const void* b){return (*(int*)a - *(int*)b);
}//计算最多可以标记的下标数组
int maxNumOfMarkedIndices(int* nums, int numsSize){//对数组进行升序排序qsort(nums, numsSize, sizeof(int), cmp);int i = 0;//指向较小值的指针int j = numsSize / 2;//指向较小值的指针int count = 0;//计数以标记的下标数目//使用双指针遍历数组while(i < numsSize / 2 && j < numsSize){if(2 * nums[i] <= nums[j]){//找到符合条件的配对,计数增加count += 2;i++;//移动小值指针j++;//移动大值指针}else{//如果条件不满足,移动大值指针j++;}}return count;
}
相关文章:
力扣刷题之2576.求出最多标记下标
题干描述 给你一个下标从 0 开始的整数数组 nums 。 一开始,所有下标都没有被标记。你可以执行以下操作任意次: 选择两个 互不相同且未标记 的下标 i 和 j ,满足 2 * nums[i] < nums[j] ,标记下标 i 和 j 。 请你执行上述操…...

黑马JavaWeb开发笔记16——请求(postman、简单参数、实体参数、@RequestParam映射)
文章目录 前言一、postman工具1. 引入2. 介绍3. 安装4. 使用 二、简单参数1. 原始方式(仅了解,以后的开发不会使用)2. SpringBoot方式3. 参数名不一致(RequestParam映射) 三、实体参数1. 简单实体对象2. 复杂实体对象 总结 前言 本篇文章是2…...
Corrupt block relative dba: 0x02c0b382 (file 11, block 45954)
接前面断电故障处理2:oracle数据库断电无法启动恢复-CSDN博客 DM00 started with pid145, OS id16516, job SYS.SYS_IMPORT_TABLE_01 2024-09-13T20:05:22.33130208:00 ADVISORY: Please collect redo for investigation of ORA-8103. Use command: ALTER SYSTE…...
二叉排序树在实际生活应用中作用
二叉排序树(Binary Search Tree, BST)在实际生活中有多种应用,主要用于需要快速查找、插入和删除操作的场景。以下是一些常见的应用领域和具体示例: 1.数据库索引 数据库系统中经常使用 BST 作为索引结构。例如,B-tr…...
单例模式的学习
示例: #ifndef TEST_H #define TEST_Hclass test { public:static test * GetINSTANCE();void print(); private:test(); };#endif // TEST_H#include "test.h" #include <QMutex> #include <QDebug> test::test() {}test *test::GetINSTANC…...

54 mysql 中各种 timeout - connect/wait/interactive/read/write_timeout
前言 在 mysql 的服务器配置中, 我们经常会使用到几个 timeout 诸如 connect_timeout, wait_timeout, interactive_timeout, read_timeout, write_timeout 等等 我们 这里来看一下 他们的具体的使用场景, 以及具体控制的相关信息 是什么 connect_timeout 这个是 客户端 和…...

实战案例(5)防火墙通过跨三层MAC识别功能控制三层核心下面的终端
如果网关是在核心设备上面,还能用MAC地址进行控制吗? 办公区域的网段都在三层上面,防火墙还能基于MAC来控制吗? 采用正常配置模式的步骤与思路 (1)配置思路与上面一样 (2)与上面区…...

【智能流体力学】数值模拟中的稳态和瞬态
在流体力学和数值模拟中, 稳态 (Steady State)意味着流体的物理量(如速度、压力、温度等)不随时间变化。换句话说,在稳态模拟中,系统已经达到了平衡,任何位置上的流场特性都不再随时间发生变化。 其他教程参考:https://doc.cfd.direct/openfoam/user-guide-v12/index…...

Vue-Route4 ts
小满学习视频 Vue-Route 官网 项目的目录结构: 1. Vue-Router的使用 安装Vue-route pnpm add vue-router4创建router文件 /route/index.vue import { createRouter } from "vue-router"; import {createMemoryHistory,createWebHashHistory,create…...

sizeof和strlen的小知识
Hello~,欢迎大家来到我的博客进行学习! 目录 1.sizeof和strlen😺1.1 sizeof🥰 1.2 strlen😋1.3 sizeof和strlen的对比👻 1.sizeof和strlen😺 1.1 sizeof🥰 sizeof是一种单目操作符,…...

Java项目: 基于SpringBoot+mybatis+maven宠物咖啡馆平台(含源码+数据库+毕业论文)
一、项目简介 本项目是一套基于SpringBootmybatismaven宠物咖啡馆平台 包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都经过严格调试,eclipse或者idea 确保可以运行! 该系统功能完善、界面美观、操作简单…...

戴尔14代服务器配置IDRAC9远程配置说明
一、规划管理网段 规划管理网段,要求如下: 管理网段与业务网段不能使用同一网段;管理网段与业务网段不能直接互通;如有条件管理网与业务网使用不同设备接入。 二、配置服务器idrac 2.1、确认idrac口位置 2.2、开机进F2 2.3、 …...
如何让你家里的电脑连接公司的远程桌面
在远程工作日益普遍的今天,能够从家里的电脑连接到公司的远程桌面,不仅可以提高工作效率,还能确保工作的连续性和数据的安全性。本文将详细指导你如何设置并实现从家中电脑连接至公司远程桌面的过程,无论你是使用Windows还是Mac系…...

软件:分享8个常用视频剪辑免费软件,你都用过吗?
随着视频剪辑的需求增多,现在市面上都有很多好用的视频剪辑软件,有的收费有的免费,不同的视频剪辑软件有不同的特点和优势。本文整理了几个简单好用的电脑视频剪辑工具,供大家参考。 不同的剪辑技术对应了不同的视频剪辑软件&…...

TS 常用类型
我们经常说TypeScript是JavaScript的一个超级 TypeScript 常用类型 TypeScript 是 JS 的超集,TS 提供了 JS 的所有功能,并且额外的增加了:类型系统 所有的 JS 代码都是 TS 代码 JS 有类型(比如,number/string 等&…...
半导体芯闻--20240913
1、舜宇光学在2024年上半年业绩表现亮眼,营收和净利润同比大幅增长。公司资产规模维持较高水平,短期偿债能力强。研发投入持续增加,特别是在车载模组领域取得显著成绩,与多家主流平台方案厂商深度合作,巩固了其在车载模…...

C盘空间不足如何解决?解决C盘空间不足的7个方法
当计算机的C盘(通常作为系统盘)空间不足时,会严重影响系统的运行效率和稳定性。针对这一问题,以下7个解决方案,可以帮助我们有效释放C盘空间,提升系统性能。 1.磁盘清理 利用Windows内置的磁盘清理工具…...

比 GPT-4 便宜 187 倍的Mistral 7B (非广告)
Mistral 7B 是一种设计用来快速处理较长文本的人工智能模型。它采用了一些特别的技术来提高速度和效率,比如“分组查询注意力(grouped-query attention)”和“滑动窗口注意力(sliding-window attention)”。 这些技术…...

FFmpeg与OpenCV联合开发
本文讲述如何利用FFmpeg SDK与OpenCV 从RTSP流中获取图像(OpenCV MAT 对象格式)。 一,构造RTSP视频流 因为是在本机实验,所以我自己构造了一个RTSP流。如果你有现成的RTSP流也可以的。 实验用的源视频是黑神话悟空的《云宫讯音》…...

Docker 部署 Redis (图文并茂超详细)
部署 Redis ( Docker ) [Step 1] : 拉取 Redis 镜像, 推荐使用 7 的 Redis 版本 docker pull redis:7.0.12[Step 2] : 创建 Redis 相关目录 ➡️ 启动 Redis 容器 ➡️ 拷贝文件 ➡️ 授权文件夹 ➡️ 删除容器 # 创建 Redis 相关目录 mkdir -p /data/redis/{conf,data,log…...

华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...

23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...