type
status
date
slug
summary
tags
category
icon
password
Property
Jul 19, 2023 05:34 AM
LeetCode-034. 在排序数组中查找元素的第⼀个和最后⼀个位置
🤔 看似o(n)其实可以偷点懒一次o(n/2)双指针梭哈，当然了，o(n)==o(n/2)
- 问题？
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
- 解答：
看似o(n)其实可以偷点懒一次o(n/2)双指针梭哈先界定边界，将边界影响的结果集先直接枚举
（1）暴力解法：
3.优化思路：
在边界内直接双指针，但是不是全量，只要每一次匹配到数据都需要扫描一下结果集，如果结果集已经完事了，直接return
就是这么简单，暴力搜索的改良版本
结果：
致谢：
有关本题的双指针的问题，欢迎您在底部评论区留言，一起交流~
- 作者:fntp
- 链接:https://polofox.com/article/leetcode-daily-1
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章