Leetcode34. 在排序数组中查找元素的第一个和最后一个位置(二分模板题)
2021/5/9 18:29:21
本文主要是介绍Leetcode34. 在排序数组中查找元素的第一个和最后一个位置(二分模板题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
解题思路
这一题可以直接看我之前总结的二分模板题,一模一样。
题目链接:ACWing789. 数的范围https://blog.csdn.net/qq_44713772/article/details/116003794
代码
class Solution { public int[] searchRange(int[] nums, int target) { if(nums.length == 0) return new int[]{-1, -1}; int l = 0, r = nums.length - 1; while(l < r) { int mid = r + l >> 1; if(nums[mid] >= target) r = mid; //代表答案在左边且包含mid这个点 else l = mid + 1; //代表答案在右边且不包含mid这个点 } int left = l; if(nums[left] != target) //如果target在数组不存在 return new int[]{-1, -1}; else { l = 0; r = nums.length - 1; while(l < r) { int mid = r + l + 1 >> 1; //加1为了防止死循环 if(nums[mid] <= target) l = mid; //代表答案在右边且包含mid这个点 else r = mid - 1; //代表答案在左边且不包含mid这个点 } return new int[]{left, r}; } } }
复杂度分析
- 时间复杂度:O(logn)
- 空间复杂度:O(1)
这篇关于Leetcode34. 在排序数组中查找元素的第一个和最后一个位置(二分模板题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验
- 2024-05-29AutoMQ 对象存储数据高效组织的秘密: Compaction
- 2024-05-29活动预告|来 GIAC 大会听大数据降本利器:AutoMQ 基于云原生重新设计的 Kafka