2576. 求出最多标记下标

news/2024/9/28 5:24:41

给你一个下标从 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

解题思路:
题目是找出两个 互不相同且未标记 的下标,一共能构成多少组
要求:1.互不相同且未标记
2.满足2 * nums[3] <= nums[0]
思路:
1.先数组排序,让数组变的有序
2.排序完后数组就变的有序了,使用双指针,左指针从0开始,右指针从1开始,那么就有了循环的依据(左指针最大是数组的长度的一半,右指针的数组长度,条件就是能组成的对数)

这里补充一点:因为数组是有序的,所以右指针右边的数一定大于左边的数,假设有对数组排序完是1,3,9....时,left = 0,right = 1时 满足2 * nums[1] <= nums[1]的条件,不用考虑nums[1]是否被标记,以为下标right 后面任何一个数都满足,循环条件 right < nums.length 不满足时,则循环也就结束了

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

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

相关文章

**** oracle 数据库-监听故障处理-故障单

**** 数据库-监听故障处理-故障单**** 数据库-监听故障处理故障反馈人张**工单接收时间2024年9月11日 9:10审核/复核人张**/张***处理完毕时间2024年9月11日 9:22报告人柏*报告时间2024年9月11日11:22故障环境IP: 180.5.115.** 数据库版本: 10.2.0.4.0故障现象告警时间: 起…

Spring声明式事务不生效?

背景 本篇博文将会讲一讲Spring中使用@Transactional注解会出现的不生效问题。事务的生效与否,一般不是我们冒烟自测的范围,测试也不会去测,但是一旦上线后,事务出现不生效的情况,就可能引发较大的问题,甚至会带来损失。所以,使用好事务注解是非常重要的,尤其是注意哪些…

一个用于管理多个 Node.js 版本的安装和切换开源工具

大家好,今天给大家分享一个用于管理多个Node.js版本的工具 NVM(Node Version Manager),它允许开发者在同一台机器上安装和使用不同版本的Node.js,解决了版本兼容性问题,为开发者提供了极大的便利。在开发环境中,特别是在处理多个项目时,每个项目可能依赖于不同版本的 N…

2552.统计上升四元组

题目描述: 给你一个长度为 n 下标从 0 开始的整数数组 nums ,它包含 1 到 n 的所有数字,请你返回上升四元组的数目。 如果一个四元组 (i, j, k, l) 满足以下条件,我们称它是上升的: 0 <= i < j < k < l < n 且 nums[i] < nums[k] < nums[j] < num…

屏幕画笔、截图工具

水豚鼠标助手 用于做屏幕指导比较方便,鼠标换肤,屏幕画笔 https://shuitunapp.com/?from=txc //官网下载pixpin下载地址 这是一款好用的屏幕截图,贴图,gif制作 小工具 https://pixpinapp.com/

disk-Linux磁盘IO性能测试方法-fio

disk-Linux磁盘IO性能测试方法-fio 测试随机写IOPS: fio -direct=1 -iodepth=128 -rw=randwrite -ioengine=libaio -bs=4k -size=10G -numjobs=1 -runtime=1000 -group_reporting -name=/path/testfile测试随机读IOPS: fio -direct=1 -iodepth=128 -rw=randread -ioengine=li…

单实例-oracle巡检模版 -20240912

单实例-oracle巡检模版 -20240912 —————————————————————————————————————————— ---- 2024年9月12日16:38:47 ---- bayaim ---- 以下内容纯属个人原创,纯属个人多年经验总结,非喜勿喷,Gun~ ——————————————————…

Yolo第Y2周:如何正确解读YOLO算法训练结果的各项指标

目录Yolo第Y2周:如何正确解读YOLO算法训练结果的各项指标weights文件夹:最终的仙丹results.png:训练总图要略loss系列:打明牌的能力box_loss 边界框损失:衡量画框cls_loss 分类损失:判断框里的物体dfl_loss 分布式焦点损失:精益求精验证集:学得好,不一定考得好精度和召…