LeetCode C++ 34. Find First and Last Position of Element in Sorted Array【Binary Search】中等
发布日期:2021-07-01 02:50:56
浏览次数:2
分类:技术文章
本文共 2021 字,大约阅读时间需要 6 分钟。
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n)
.
If the target is not found in the array, return [-1, -1]
.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6Output: [-1,-1]
Constraints:
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums
is a non decreasing array.-10^9 <= target <= 10^9
题意:在排序数组中确定数字 target
出现的左右边界。
解法1 STL
用STL的二分查找函数。代码如下:
class Solution { public: vector searchRange(vector & nums, int target) { int left = lower_bound(nums.begin(), nums.end(), target) - nums.begin(); int right = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1; if (left > right) return { -1, -1}; return vector { left, right}; }};
解法2 手写二分上下界函数
class Solution { private: //找到第一个>=v的元素的位置 int lowerBound(vector & A, int x, int y, int v) { while (x < y) { int m = x + (y - x) / 2; if (A[m] >= v) y = m; else x = m + 1; } return x; } //找到第一个>v的元素的位置 int upperBound(vector & A, int x, int y, int v) { while (x < y) { int m = x + (y - x) / 2; if (A[m] > v) y = m; else x = m + 1; } return x; }public: vector searchRange(vector & nums, int target) { if (nums.empty()) return { -1, -1}; //特判空 int n = nums.size(); int first = lowerBound(nums, 0, n, target); //第一个<= if (first >= n || nums[first] != target) return vector { -1, -1}; //特判不存在 int last = upperBound(nums, 0, n, target); //第一个< return vector { first, last - 1}; }};
运行效率如下:
执行用时:20 ms, 在所有 C++ 提交中击败了74.62% 的用户内存消耗:13.5 MB, 在所有 C++ 提交中击败了67.57% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108372747 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月08日 22时35分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
nginx: [emerg] unknown directive "if($remote_addr" in /usr/local/tools/nginx/conf/nginx.conf:57
2019-05-01
module pip has no attribute main问题解决
2019-05-01
LeetCode 134.Gas Station (加油站)
2019-05-01
Python之命名元组 (namedtuple)
2019-05-01
使用libpcap过滤arp
2019-05-01
[转帖]Robots.txt指南
2019-05-01
Eclipse + MyEclipse下配置J2EE工程(英文界面)
2019-05-01
Eclipse及其插件下载网址大全
2019-05-01
正则表达式简介(微软)--6.优先权顺序
2019-05-01
多用户与多租户的区别
2019-05-01
Python自动化运维 - day14 - JavaScript基础
2019-05-02
oracle保存小数点前为"0"的问题
2019-05-02
linux sar 命令详解
2019-05-02
ipvsadm 安装配置
2019-05-02
Linux shell脚本的字符串截取
2019-05-02
数据库复习(4)
2019-05-02
1小时点击量破千万!阿里巴巴首发:MySQL高级调优笔记!全是技术重点
2019-05-02
这个GItHub上的Java项目开源了 2021最全的Java架构面试复习指南
2019-05-02