力扣刷题之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…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
