当前位置: 首页 > 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…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...

WEB3全栈开发——面试专业技能点P4数据库

一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库&#xff0c;基于 mysql 库改进而来&#xff0c;具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点&#xff1a; 支持 Promise / async-await&#xf…...