去掉数组最后一个元素_【一天一大 lee】在排序数组中查找元素的第一个和最后一个位置 (难度:中等) Day20201201...
发布日期:2021-06-24 10:02:27
浏览次数:3
分类:技术文章
本文共 2017 字,大约阅读时间需要 6 分钟。
题目:
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
进阶:
- 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?
示例:
- 示例 1:
输入:nums = [5,7,7,8,8,10], target = 8 输出:[3,4]
- 示例 2:
输入:nums = [5,7,7,8,8,10], target = 6 输出:[-1,-1]
- 示例 3:
输入:nums = [], target = 0 输出:[-1,-1]
提示:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一个非递减数组
- -109 <= target <= 109
抛砖引玉
思路:
一遍循环
一遍循环,记录数组中等于 target 元素的位置,如果变量到元素大于 target,则终止循环,直接返回结果
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var searchRange = function(nums, target) { let start = -1, end = -1, index = 0 while (index if (nums[index] === target) { if (start === -1) { start = index end = index } else { end = index } index++ } else if (nums[index] > target) { return [start, end] } else { index++ } } return [start, end] }
二分查找
首先二分查找出 target 所在的索引位置:
- 如果没有找到则返回[-1,-1]
- 如果找到了索引位置,则在这个索引位置的前后继续查找,找到边界索引位置
var searchRange = function(nums, target) { let start = -1, end = nums.length - 1, mid = Math.floor((start + end) / 2), flag = false // 找到数组中target的位置 while (start <= end) { mid = (start + end) / 2 if (nums[mid] start = mid + 1 } else if (nums[mid] > target) { end = mid - 1 } else { flag = true break } } // 找到target边界索引位置 if (flag) { let left = mid, right = mid while (left - 1 >= 0 && nums[left - 1] == target) { left-- } while (right + 1 <= nums.length - 1 && nums[right + 1] == target) { right++ } return [left, right] } else { return [-1, -1] } }
博客: 前端小书童
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公众号:前端小书童
转载地址:https://blog.csdn.net/weixin_31990755/article/details/112613877 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年03月30日 19时39分01秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
AcWing - 高精度加法(大数加法)
2019-04-28
AcWing - 高精度减法(大数减法)
2019-04-28
AcWing - 高精度乘法(大数乘法)
2019-04-28
AcWing - 高精度除法(大数除法)
2019-04-28
AcWing - 前缀和(前缀和)
2019-04-28
AcWing - 子矩阵的和(二维前缀和)
2019-04-28
AcWing - 差分(一维差分)
2019-04-28
AcWing - 最长连续不重复子序列(双指针)
2019-04-28
AcWing - 数组元素的目标和(双指针)
2019-04-28
AcWing - 区间和(离散化&前缀和)
2019-04-28
AcWing - 区间合并(贪心)
2019-04-28
AcWing - 单链表(模拟)
2019-04-28
AcWing - 双链表(模拟)
2019-04-28
AcWing - KMP字符串(KMP)
2019-04-28
来一个总结吧
2019-04-28
有趣的句子
2019-04-28
每天一道 python 面试题 - Python中的元类(metaclass) 详细版本
2019-04-28
Scrapy(6)Item loader 加载器详解
2019-04-28
每日一道python面试题 - Python的实例,类和静态方法揭秘
2019-04-28
今日金融词汇---新股新债前面的N,是什么?
2019-04-28