LeetCode 34. Find First and Last Position of Element in Sorted Array
2022/3/10 23:16:40
本文主要是介绍LeetCode 34. Find First and Last Position of Element in Sorted Array,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LeetCode 34. Find First and Last Position of Element in Sorted Array ()
题目
链接
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
问题描述
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
进阶:
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?
示例
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
提示
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
思路
同样是基础的二分查找,我们需要注意的就是,这个既要求左边界又要求右边界,为了避免出现错误,我用了两段分别求左右,然后判断是否符合条件。
复杂度分析
时间复杂度 O(logn) 空间复杂度 O(1)
代码
Java
public int[] searchRange(int[] nums, int target) { int[] ans = new int[2]; int left1 = 0, left2 = 0; int right1 = nums.length - 1, right2 = nums.length - 1; while (left1 <= right1) { int mid = left1 + (right1 - left1) / 2; if (nums[mid] < target) { left1 = mid + 1; } else if (nums[mid] > target) { right1 = mid - 1; } else if (nums[mid] == target) { right1 = mid - 1; } } ans[0] = left1; while (left2 <= right2) { int mid = left2 + (right2 - left2) / 2; if (nums[mid] < target) { left2 = mid + 1; } else if (nums[mid] > target) { right2 = mid - 1; } else if (nums[mid] == target) { left2 = mid + 1; } } ans[1] = right2; if (left1 >= nums.length || nums[left1] != target || right2 < 0 || nums[right2] != target) { ans[0] = -1; ans[1] = -1; return ans; } return ans; }
这篇关于LeetCode 34. Find First and Last Position of Element in Sorted Array的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享