LeetCode 每日一题 求出最多标记下标

求出最多标记下标

题目如下↓

给你一个下标从 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 。
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 109

解题思路

题目的意思就是在数组里面找一对数,这一对数中大的数大于等于小的数的两倍,我们需要返回最多可以有多少对数

那么既然是一个小的数与大的数进行配对,那么我们不如先用 qsort() 对数组进行排序

然后我们接着对题目进行分析,有一个想法是先找到最小的数,然后再找到最小的可以与之配对的数,但是这样做可以找到最多的对数吗?例如数组 [2,4,5,9] 如果按照上述想法,那么就只有一对(2,4),但是实际上可以有(2,5)(4,9)两对,所以上述想法存在问题

我们换一个思路,对于一个数组,最好的情况就是所有的数都可以配对或者只留下一个数,那么我们不如将排好序的数组平分为两个区域,左边的区域与右边的区域进行配对,也就是从左区域的最小数开始寻找右区域的可以配对的数,利用双指针进行枚举,即可找到最多的对数。

那么为什么我们的第一个想法不对呢?

因为我们直接去找可以配对的最小数字,有可能是左边区域的两个数进行了配对,然而因为右边区域的所有数字都比左边大,所以左边配对的较小的数一定可以在右边找到数配对,另一个较大的数也有可能与右边区域进行配对,这样就导致少了一个可能配对的机会,导致对数不一定是最大。另外,由于左边与右边的数字的数量最多只差1,所以左边的数只与右边的数进行配对并不会导致最多配对数的变小。

下面上代码!

int maxNumOfMarkedIndices(int* nums, int numsSize){int s=0;int compare(int*a,int*b){return *a - *b;}qsort(nums,numsSize,sizeof(int),compare);int m = numsSize/2;int l=0,r=m;while(l<m && r<numsSize){if(nums[r]>=nums[l]*2){s+=2;l++;r++;}else{r++;}}return s;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/144761.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Vue3实战:使用 errorHandler 捕获全局错误

你好同学&#xff0c;我是沐爸&#xff0c;欢迎点赞、收藏、评论和关注。 在 Vue3 中&#xff0c;app.config.errorHandler 是一个错误处理器&#xff0c;用于为应用内抛出的未捕获错误指定一个全局处理函数&#xff0c;它接收三个参数&#xff1a;错误对象、触发该错误的组件…

什么品牌超声波清洗机质量好?四大绝佳超声波清洗机品牌推荐!

在快节奏的现代生活中&#xff0c;个人物品的清洁卫生显得至关重要。眼镜、珠宝饰品、手表乃至日常餐厨用具&#xff0c;这些频繁接触的物品极易累积污渍与细菌。拿眼镜为例&#xff0c;缺乏定期清洁会让油渍与尘埃积累&#xff0c;进而成为细菌的温床&#xff0c;靠近眼睛使用…

人脸识别系统+电插锁安装配置过程

一、适用场景 1、各住宅小区内&#xff0c;一个单元涉及多户&#xff0c;一楼安装公共的人脸识别门禁进行身份的认证。 2、某企业的职工住宅区&#xff0c;企业统一安装人脸识别门禁认证身份。 3、自建楼栋&#xff0c;分多间出租给住户时&#xff0c;每个住户配备电子钥匙存在…

GEE使用require函数调用自己的Js库

新建了一个repository&#xff0c;名为Lib 把我的地形校正的函数放了进去 在自己的代码中调用就用到这个路径&#xff0c;主要Lib后面用冒号

观《中国数据库前世今生》有感:从历史到未来的技术变迁

观《中国数据库前世今生》有感&#xff1a;从历史到未来的技术变迁 在数字化浪潮中&#xff0c;数据库技术作为信息化建设的核心&#xff0c;承载了时代发展的脉搏。观看了纪录片《中国数据库前世今生》后&#xff0c;我深深感受到了中国数据库技术从无到有、从追赶到引领的艰…

深度残差网络ResNet简介

【图书推荐】《PyTorch深度学习与企业级项目实战》-CSDN博客 《PyTorch深度学习与企业级项目实战&#xff08;人工智能技术丛书&#xff09;》(宋立桓&#xff0c;宋立林)【摘要 书评 试读】- 京东图书 (jd.com) 卷积神经网络经典模型架构简介-CSDN博客 深度残差网络&#xf…

10分钟搞清楚为什么Transformer中使用LayerNorm而不是BatchNorm

1. Norm(Normalization) 首先&#xff0c;LayerNorm和BatchNorm的Norm是Normalization的缩写,不是Norm-范数。 Normalization在统计学中一般翻译为归一化&#xff0c;还有类似的是Standardization&#xff0c;一般翻译成标准化。这两个概念有什么区别呢&#xff1f; 归一化是…

vue2 + moment 实现日历,并带有上个月和下个月日期的日历

在 Vue 2 中使用 moment 库绘制一个带有上个月和下个月日期的日历&#xff0c;可以通过以下步骤实现。这个日历将显示当前月份的天数&#xff0c;以及前一个月和下一个月的部分日期&#xff08;通常为了让日历对齐为6行&#xff0c;每行7天&#xff09;。 主要步骤&#xff1a…

海睿思ABI——不只是BI,更多的是数据和智能

在当今这个数据洪流席卷各行各业的数字化时代&#xff0c;企业BI的建设已不再是可选项&#xff0c;而是驱动企业转型升级、实现精细化运营的必由之路。传统BI通过临时数据集直连业务系统&#xff0c;仅能展示预设报表和仪表盘&#xff0c;难以集成异构数据源&#xff0c;适应业…

【数学二】函数概念、常用函数、函数四大性质

考试要求 1、理解函数的概念&#xff0c;掌握函数的表示法&#xff0c;并会建立应用问题的函数关系. 2、了解函数的有界性、单调性、周期性和奇偶性. 3、理解复合函数及分段函数的概念、了解反函数及隐函数的概念。 4、掌握基本初等函数的性质及其图形、了解初等函数的概念。…

SpringCloud从零开始简单搭建 - JDK17

文章目录 SpringCloud Nacos从零开始简单搭建 - JDK17一、创建父项目二、创建子项目三、集成Nacos四、集成nacos配置中心 SpringCloud Nacos从零开始简单搭建 - JDK17 环境要求&#xff1a;JDK17、Spring Boot3、maven。 那么&#xff0c;如何从零开始搭建一个 SpringCloud …

PyQGIS开发 3 基础功能开发

PyQGIS开发 3 基础功能开发 1 添加图层树与地图视图 1.1 添加控件 1.2 Python代码 from PyQt5.QtCore import QMimeData from qgis.PyQt.QtWidgets import QMainWindow from qgis._core import QgsMapLayer, QgsRasterLayer, QgsVectorLayer from qgis.core import QgsProje…

美联储降息引爆股市,标普500指数逼近历史新高

在美联储宣布大幅降息后&#xff0c;股市迎来了强劲反弹。投资者信心大增&#xff0c;此前他们就预期美联储会降息0.5个百分点。周四的股市涨幅让标普500指数接近历史收盘最高点。 周四&#xff0c;标普500指数有望刷新历史纪录&#xff0c;此前美联储的大幅降息为市场注入了活…

基于STM32的智能门禁系统(指纹、蓝牙、刷卡、OLED、电机)

目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于STM32单片机&#xff0c;六个按键&#xff0c;分别代表指纹、蓝牙、刷卡的正确进门与错误进门&#xff1b; 比如第一个按键按下&#xff0c;表示指纹正确&#xff0c;OLED显示指纹正确&#x…

OpenHarmony(鸿蒙南向开发)——小型系统内核(LiteOS-A)【内核启动】

往期知识点记录&#xff1a; 鸿蒙&#xff08;HarmonyOS&#xff09;应用层开发&#xff08;北向&#xff09;知识点汇总 鸿蒙&#xff08;OpenHarmony&#xff09;南向开发保姆级知识点汇总~ 子系统开发内核 轻量系统内核&#xff08;LiteOS-M&#xff09; 轻量系统内核&#…

faiss安装 (CPU版本)

faiss版本 faiss-v1.7.4 cd faiss-v1.7.4cmake -B build . -DBUILD_TESTINGOFF -DFAISS_ENABLE_GPUOFF -DFAISS_ENABLE_PYTHONOFFmake -C build -j faiss&#xff1b; 默认安装路径如下 -- Installing: /usr/local/lib64/libfaiss.a -- Installing: /usr/local/include/faiss…

跨境平台通用测评技巧:解锁Temu、亚马逊等平台的销量密码

在当今竞争激烈的跨境电商行业&#xff0c;测评补单虽被视为“公开的秘密”&#xff0c;但无论是消费者还是平台方对此普遍持有反感态度。对于新手店铺而言&#xff0c;若缺乏价格和运营等方面的绝对优势&#xff0c;要在市场中生存下去尤为困难。因此&#xff0c;合理使用测评…

深入探讨IDSIPS:信息安全的未来趋势与应用

引言 在信息技术飞速发展的今天&#xff0c;网络安全问题愈发突出。随着数据泄露、网络攻击等事件频发&#xff0c;企业和个人对信息安全的重视程度不断提高。IDSIPS&#xff08;Intrusion Detection System and Intrusion Prevention System&#xff09;作为信息安全领域的重…

PowerShell install 一键部署Oracle12c

Oracle12c前言 Oracle 12c是甲骨文公司推出的一款关系数据库管理系统,它引入了多项创新特性,如多租户架构、大数据处理和云部署,适用于企业级应用。以下是Oracle 12c的详细介绍: Oracle 12c的主要特点 高性能:通过多线程处理、自动优化等技术,提高了数据库的查询和处理…

非标工业模型评审不再难,3D一览通助力高效协同

在当今工业领域&#xff0c;非标设备设计正成为满足特定客户需求的关键。这类设计服务涉及为特定应用场景量身定制的设备或机器&#xff0c;它们通常不是市场上现成的标准化产品&#xff0c;而是根据客户的独特需求进行个性化设计和制造。 这种定制化过程要求设计团队与客户进…