《每日一题》34. 在排序数组中查找元素的第一个和最后一个位置
发布日期:2022-03-18 05:04:17
浏览次数:4
分类:技术文章
本文共 1486 字,大约阅读时间需要 4 分钟。
思路:利用二分法,先左边界,后右边界
class Solution {public: vector searchRange(vector & nums, int target) { int leftBorder = getLeftBorder(nums, target); int rightBorder = getRightBorder(nums, target); // 情况一 if (leftBorder == -2 || rightBorder == -2) return {-1, -1}; // 情况三 if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1}; // 情况二 return {-1, -1}; }private: int getRightBorder(vector & nums, int target) { int left = 0; int right = nums.size() - 1; int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况 while (left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] > target) { right = middle - 1; } else { // 寻找右边界,nums[middle] == target的时候更新left left = middle + 1; rightBorder = left; } } return rightBorder; } int getLeftBorder(vector & nums, int target) { int left = 0; int right = nums.size() - 1; int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况 while (left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] >= target) { // 寻找左边界,nums[middle] == target的时候更新right right = middle - 1; leftBorder = right; } else { left = middle + 1; } } return leftBorder; }};
转载地址:https://blog.csdn.net/qq_40911499/article/details/123352644 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年03月01日 06时40分22秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
linux英文包安装教程视频,Linux源码包安装过程讲解
2019-04-21
linux 关闭rsync服务器,linux下配置rsync服务器和实时同步
2019-04-21
linux初始化TCP服务失败,深入Linux系统追踪TCP初始化
2019-04-21
linux下vi编辑器的命令大全,linux下VI编辑器命令大全(超级完整版)
2019-04-21
C语言极坐标转直角坐标,C语言实现直角坐标转换为极坐标的方法
2019-04-21
16F877A和24C02通信汇编语言,PIC16f877A读写24c02程序
2019-04-21
用c语言编写小于n的所有素数,关于求N以内素数的一点小问题(N小于一亿)
2019-04-21
华为100万部鸿蒙,2019年Q4发布 华为100万部鸿蒙OS手机已开测
2019-04-21
html5 video视频资源保护,HTML5 视频播放 <video>
2019-04-21
编程之类的文案_如何锻炼写文案的能力?
2019-04-21
vscode 不能使用中文输入法_vscode中vim插件设置
2019-04-21
当集合a为空集时a的取值范围_1.1.2 集合间的基本关系
2019-04-21