Leetcode刷题笔记6

34. 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)

解法一:暴力查找

[1, 2, 3, 3, 3, 4, 5] t = 3
从前往后扫描暴力查找,最坏情况下O(N)

优化
利用数组有序的特性

解法二:朴素二分

[1, 2, 3, 3, 3, 4, 5] t = 3
 L           M        R
在极端情况下时间复杂度会降低,比如如果数组内的元素都一样

优化
[1, 2, 3, 3, 3, 4, 5] t = 3
[           ] [            ]
左边区间小于t,右边区间大于等于t

当发现问题中有二段线的规律时就可以用二分查找

 L             M             R
[-----------------------------] t
               x


查找区间左端点

1. x < t -> left = mid + 1 -> [left,right]

2. x >= t -> right = mid -> [left, right] 

因为 mid有可能是最终结果,所以不能更新到 mid + 1

细节处理:

1. 循环条件
left < right

a. 当 left = right的时候就是最终结果,无需判断
b. 如果判断,就会死循环

第一种情况:[left, right]中有结果
 L                               R
[-----------------------------] t
[            ][                    ]         
           t
因为 left = mid + 1,所以 left是想跳出左边这个区域的
当left和right相遇的位置就是最终结果

第二种情况:全大于t
 L                              R
[-----------------------------] t
只会命中第二个条件,right只会像左移动
直接判断左端点的值是否是t

第三种情况:全小于t
只会命中第一个条件,left只会像右移动
直接判断右端点的值是否是t

2. 求中点的操作
a. left + (right - left) / 2
b. left + (right - left + 1) / 2
当数组的个数是偶数时,用a求中点是靠左,用b是靠右

用b会陷入死循环,因为是右端点

当a。求的是左端点,当命中第一个条件时left会右移,此时相等的话就终止循环
当命中第二个条件时,right会更新到mid,此时两个又相遇了,又终止循环了
所以求中点的操作只能用a才能终止循环

查找区间右端点

[1, 2, 3, 3, 3, 4, 5] t = 3
[                    ][    ]

左边区间全部小于等于t,右边全部大于t

 L             M             R
[-----------------------------] t
                x
1. x <= t,mid此时在左边区域,所以更新left -> left = mid -> [left, right] left和right中继续寻找结果

2. x > t,mid此时在右边区域,更新right -> right = mid - 1 -> [left, right]

处理细节:
1. 循环条件
left < right

2. 求中点的方式
a. left + (right - left) / 2
b. left + (right - left + 1) / 2

b求的是右端点
当最后元素剩2个时
[* *]
 L R

如果使用a,那么mid现在落在L,那么对于第一个条件,left会在这里不动,然后mid又落在这个位置,就会陷入死循环
使用b,mid就在R,当命中第一个条件时,left会移动到right,终止循环
命中第二个条件,right移动到left,也会终止循环

代码:C++

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {// 处理边界情况if(nums.size() == 0) return {-1, -1};int begin = 0;// 1. 二分左端点int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2; // 中点下标if(nums[mid] < target) left = mid + 1;else right = mid;}// 结束循环后,left和right相遇// 判断是否有结果if(nums[left] != target) return {-1, -1};else begin = left; // 等于left或right都一样,标记左端点// 2. 二分右端点// 其实left不需要重置,但是为了保持代码的独立性left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2; // 中点下标if(nums[mid] <= target) left = mid;else right = mid - 1;}return {begin, right}; // 此时left或者right都存的右端点}
};

当下面出现 -1 的时候,上面就 +1
分类讨论的代码,就题论题即可

查找区间左端点的模版

// 查找区间左端点的模版
while (left < right)
{int mid = left + (right - left) / 2;if (...) left = mid + 1;else right = mid;
}

 查找区间右端点的模版

// 查找区间右端点的模版
while (left < right)
{int mid = left + (right - left + 1) / 2;if (...) left = mid;else right = mid - 1;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

TCP的重传机制

TCP 是一个可靠的传输协议&#xff0c;解决了IP层的丢包、乱序、重复等问题。这其中&#xff0c;TCP的重传机制起到重要的作用。 序列号和确认号 之前我们在讲解TCP三次握手时&#xff0c;提到过TCP包头结构&#xff0c;其中有序列号和确认号&#xff0c; 而TCP 实现可靠传输…

Artifactory清理二进制文件丢失的制品

一、摘要 当制品上传到 Artifactory 时&#xff0c;Artifactory 会在数据库中记录制品的相关元数据信息&#xff0c;包括文件路径、大小、校验和&#xff08;如 MD5、SHA1&#xff09;、上传时间、索引、依赖等。实际的制品二进制文件会存储在指定的存储后端&#xff0c;具体的…

基于Java+SpringBoot+Mybaties-plus+Vue+elememt + uniapp 新闻资讯 的设计与实现

一.项目介绍 本系统分为 后端 和 小程序端 后端&#xff1a;点击登录按钮 设置个人中心、 管理员账号数据维护、 基础数据维护、 短视频信息维护(包括查看短视频留言、短视频收藏)、 论坛维护(增删改查帖子信息&#xff0c;包括查…

docker查看容器目录挂载

查看命令 docker inspect --format{{ json .Mounts }} <container_id_or_name> | jq 示例 docker inspect --format{{ json .Mounts }} af656ae540af | jq输出

一篇文章让你学会专注

专注&#xff0c;字典的释义是&#xff1a;专心注意&#xff1b;精神贯注。 我个人理解的是&#xff1a;用力屏蔽无关的事物&#xff0c;全身心力地专门注意一个事物。 你关心的&#xff0c;才能注意到&#xff0c;注意到了&#xff0c;才能故意地注意&#xff0c;进而全身心力…

【Linux-RTC】

Linux-RTC ■ rtc_device 结构体■ RTC 时间查看与设置■ 1、时间 RTC 查看■ 2、设置 RTC 时间 ■ rtc_device 结构体 Linux 内核将 RTC 设备抽象为 rtc_device 结构体 rtc_device 结构体&#xff0c;此结构体定义在 include/linux/rtc.h 文件中 ■ RTC 时间查看与设置 ■ 1…

服务器主板电池

一、什么是服务器纽扣电池&#xff1f; 服务器纽扣电池&#xff0c;也叫CMOS电池&#xff0c;是一种非常小型的电池&#xff0c;通常与服务器主板上的CMOS芯片相结合&#xff0c;用于储存BIOS设置、时钟和其他关键系统信息。这种电池的体积通常比一枚硬币还小&#xff0c;而且…

d3dcompiler43.dll丢失怎么修复,分享几种有效的修复教程

电脑已经成为我们生活中不可或缺的一部分。然而&#xff0c;由于各种原因&#xff0c;电脑可能会出现一些问题&#xff0c;其中之一就是d3dcompiler43.dll文件丢失。这个文件是DirectX组件之一&#xff0c;用于编译和链接DirectX应用程序。当这个文件丢失时&#xff0c;可能会导…

DataCube 漏洞小结

在这里分享一下通过拖取 DataCube 代码审计后发现的一些漏洞&#xff0c;包括前台的文件上传&#xff0c;信息泄露出账号密码&#xff0c;后台的文件上传。当然还有部分 SQL 注入漏洞&#xff0c;因为 DataCube 采用的是 SQLite 的数据库&#xff0c;所以SQL 注入相对来说显得就…

MAB规范(2):Introduction 介绍

Chapter1 Introduction 1.1 指南目的 MathWorks咨询委员会&#xff08;MAB&#xff09;指南规定了Simulink和Stateflow建模的重要基本规则。这些建模指南的总体目的是让建模者和控制系统模型的使用者能够简单、共同地理解。 指南的主要目标是&#xff1a; • 可读性  提高…

Ubuntu 安装好虚拟环境后,找不到workon 命令

1、安装虚拟环境 pip3 install virtualenv pip3 install virtualenvwrapper 2、安装完成后 workon 命令。 找不到workon 命令 执行&#xff0c;source virtualenvwrapper.sh 执行后&#xff0c;在使用workon命令&#xff0c;即可完成。

day-36 删除链表的倒数第 N 个结点

思路 首先计算出链表的长度&#xff0c;然后删除第n个节点即可&#xff0c;但要注意考虑特殊情况 解题方法 特殊情况&#xff1a;1.删除节点为最后一个节点 2.删除节点为头结点 Code /*** Definition for singly-linked list.* public class ListNode {* int val;* …

MySQL十部曲之九:MySQL优化理论

文章目录 前言概述查询优化查询执行计划EXPLAIN获取表结构信息获取执行计划信息 EXPLAIN 输出格式如何使用EXPLAIN进行优化 范围访问优化单列索引的范围访问多列索引的范围访问 索引合并优化索引合并交叉访问算法索引合并联合访问算法索引合并排序联合访问算法 索引下推优化连接…

使用LeanCloud平台的即时通讯

LeanCloud 是领先的 Serverless 云服务&#xff0c;为产品开发提供强有力的后端支持&#xff0c;旨在帮助开发者降低研发、运营维护等阶段投入的精力和成本。 LeanCloud 整合了各项服务&#xff0c;让开发者能够聚焦在核心业务上&#xff0c;为客户创造更多价值。 *即时通讯 …

5月29日-shell复习

一.Shell概述 1&#xff09;Linux提供的Shell解析器有&#xff1a;sudo cat /etc/shells /bin/sh /bin/bash /usr/bin/sh /usr/bin/bash /bin/tcsh /bin/csh 2&#xff09;bash和sh的关系 cd /bin ll | grep bash 或者使用&#xff1a;ls -l /bin/ | grep bash 3&#xff0…

深入pandas:数据分析

目录 前言 第一点&#xff1a;导入模块 第二点&#xff1a;准备数据 第三点&#xff1a;简单的分析数据 第四点&#xff1a;【重点】数据透支 总结 前言 在数据分析与挖掘的领域&#xff0c;了解如何使用工具和方法来探索数据是至关重要的。本文将探讨如何利用Python中的…

MAB规范(1):概览介绍

前言 MATLAB的MAAB&#xff08;MathWorks Automotive Advisory Board&#xff09;建模规范是一套由MathWorks主导的建模指南&#xff0c;旨在提高基于Simulink和Stateflow进行建模的代码质量、可读性、可维护性和可重用性。这些规范最初是由汽车行业的主要厂商共同制定的&…

如何使用宝塔面板搭建Tipask问答社区网站并发布公网远程访问

文章目录 前言1.Tipask网站搭建1.1 Tipask网站下载和安装1.2 Tipask网页测试1.3 cpolar的安装和注册 2. 本地网页发布2.1 Cpolar临时数据隧道2.2 Cpolar稳定隧道&#xff08;云端设置&#xff09;2.3 Cpolar稳定隧道&#xff08;本地设置&#xff09; 3. 公网访问测试4.结语 前…

FreeRTOS基础(四):静态创建任务

上一篇博客&#xff0c;我们讲解了FreeRTOS中如何动态创建任务&#xff0c;那么这一讲&#xff0c;我们从实战出发&#xff0c;规范我们在FreeRTOS下的编码风格&#xff0c;掌握静态创建任务的编码风格&#xff0c;达到实战应用&#xff01; 目录 一、空闲任务和空闲任务钩子…

MT8781安卓核心板_MTK联发科Helio G99核心板规格参数

MT8781安卓核心板采用先进的台积电6纳米级芯片生产工艺&#xff0c;配备高性能Arm Cortex-A76处理器和Arm Mali G57 GPU&#xff0c;加上LPDDR4X内存和UFS 2.2存储&#xff0c;在处理速度和数据访问速度上都有着出色的表现。 MT8781还支持120Hz显示器&#xff0c;无需额外的DSC…