二哥的 LeetCode 刷题笔记，第 34 题：在排序数组中查找元素的第一个和最后一个位置
鲁迅曾说，笑傲江湖其实讲的就是最真实的人性，有些人明明做了坏事，却能装出一副正义凛然的样子，有些人明明做了好事，却被人说成是坏人。这就是江湖，这就是人性。如果你想不被人欺负，就要学会自强自立，不依赖别人。对于程序员来说，笔试想要取得好成绩，多刷一点 LeetCode 也是应该的。
题意
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
难度
中等
示例
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
输入：nums = [], target = 0
输出：[-1,-1]
分析 1
在排序数组中查找元素的第一个和最后一个位置，如果不考虑时间复杂度的话，会非常简单。
第一次遍历，从左到右找到第一个等于 target 的元素，记录下它的位置；第二次遍历，从右到左找到第一个等于 target
1人已点赞
1 条评论
回复