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

力扣刷题之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 。 一开始&#xff0c;所有下标都没有被标记。你可以执行以下操作任意次&#xff1a; 选择两个 互不相同且未标记 的下标 i 和 j &#xff0c;满足 2 * nums[i] < nums[j] &#xff0c;标记下标 i 和 j 。 请你执行上述操…...

黑马JavaWeb开发笔记16——请求(postman、简单参数、实体参数、@RequestParam映射)

文章目录 前言一、postman工具1. 引入2. 介绍3. 安装4. 使用 二、简单参数1. 原始方式&#xff08;仅了解&#xff0c;以后的开发不会使用&#xff09;2. SpringBoot方式3. 参数名不一致(RequestParam映射) 三、实体参数1. 简单实体对象2. 复杂实体对象 总结 前言 本篇文章是2…...

Corrupt block relative dba: 0x02c0b382 (file 11, block 45954)

接前面断电故障处理2&#xff1a;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…...

二叉排序树在实际生活应用中作用

二叉排序树&#xff08;Binary Search Tree, BST&#xff09;在实际生活中有多种应用&#xff0c;主要用于需要快速查找、插入和删除操作的场景。以下是一些常见的应用领域和具体示例&#xff1a; 1.数据库索引 数据库系统中经常使用 BST 作为索引结构。例如&#xff0c;B-tr…...

单例模式的学习

示例&#xff1a; #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识别功能控制三层核心下面的终端

如果网关是在核心设备上面&#xff0c;还能用MAC地址进行控制吗&#xff1f; 办公区域的网段都在三层上面&#xff0c;防火墙还能基于MAC来控制吗&#xff1f; 采用正常配置模式的步骤与思路 &#xff08;1&#xff09;配置思路与上面一样 &#xff08;2&#xff09;与上面区…...

【智能流体力学】数值模拟中的稳态和瞬态

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

Vue-Route4 ts

小满学习视频 Vue-Route 官网 项目的目录结构&#xff1a; 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~,欢迎大家来到我的博客进行学习&#xff01; 目录 1.sizeof和strlen&#x1f63a;1.1 sizeof&#x1f970; 1.2 strlen&#x1f60b;1.3 sizeof和strlen的对比&#x1f47b; 1.sizeof和strlen&#x1f63a; 1.1 sizeof&#x1f970; sizeof是一种单目操作符&#xff0c…...

Java项目: 基于SpringBoot+mybatis+maven宠物咖啡馆平台(含源码+数据库+毕业论文)

一、项目简介 本项目是一套基于SpringBootmybatismaven宠物咖啡馆平台 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操作简单…...

戴尔14代服务器配置IDRAC9远程配置说明

一、规划管理网段 规划管理网段&#xff0c;要求如下&#xff1a; 管理网段与业务网段不能使用同一网段&#xff1b;管理网段与业务网段不能直接互通&#xff1b;如有条件管理网与业务网使用不同设备接入。 二、配置服务器idrac 2.1、确认idrac口位置 2.2、开机进F2 2.3、 …...

如何让你家里的电脑连接公司的远程桌面

在远程工作日益普遍的今天&#xff0c;能够从家里的电脑连接到公司的远程桌面&#xff0c;不仅可以提高工作效率&#xff0c;还能确保工作的连续性和数据的安全性。本文将详细指导你如何设置并实现从家中电脑连接至公司远程桌面的过程&#xff0c;无论你是使用Windows还是Mac系…...

软件:分享8个常用视频剪辑免费软件,你都用过吗?

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

TS 常用类型

我们经常说TypeScript是JavaScript的一个超级 TypeScript 常用类型 TypeScript 是 JS 的超集&#xff0c;TS 提供了 JS 的所有功能&#xff0c;并且额外的增加了&#xff1a;类型系统 所有的 JS 代码都是 TS 代码 JS 有类型&#xff08;比如&#xff0c;number/string 等&…...

半导体芯闻--20240913

1、舜宇光学在2024年上半年业绩表现亮眼&#xff0c;营收和净利润同比大幅增长。公司资产规模维持较高水平&#xff0c;短期偿债能力强。研发投入持续增加&#xff0c;特别是在车载模组领域取得显著成绩&#xff0c;与多家主流平台方案厂商深度合作&#xff0c;巩固了其在车载模…...

C盘空间不足如何解决?解决C盘空间不足的7个方法

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

比 GPT-4 便宜 187 倍的Mistral 7B (非广告)

Mistral 7B 是一种设计用来快速处理较长文本的人工智能模型。它采用了一些特别的技术来提高速度和效率&#xff0c;比如“分组查询注意力&#xff08;grouped-query attention&#xff09;”和“滑动窗口注意力&#xff08;sliding-window attention&#xff09;”。 这些技术…...

FFmpeg与OpenCV联合开发

本文讲述如何利用FFmpeg SDK与OpenCV 从RTSP流中获取图像&#xff08;OpenCV MAT 对象格式&#xff09;。 一&#xff0c;构造RTSP视频流 因为是在本机实验&#xff0c;所以我自己构造了一个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…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...