当前位置: 首页> 教育> 锐评 > behance网站_黑龙江省建设厅官网_线下推广渠道和方式_推广软文发稿

behance网站_黑龙江省建设厅官网_线下推广渠道和方式_推广软文发稿

时间:2025/7/10 17:29:30来源:https://blog.csdn.net/apple_74262176/article/details/143690077 浏览次数:0次
behance网站_黑龙江省建设厅官网_线下推广渠道和方式_推广软文发稿

文章目录

      • 1. 题目链接
      • 2. 题目大意
      • 3. 示例
      • 4. 解题思路
      • 参考代码

1. 题目链接

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)



2. 题目大意

描述:给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target

要求:找出给定目标值在数组中的开始位置和结束位置。

说明

  • 要求使用时间复杂度为 O(log⁡n) 的算法解决问题。


3. 示例

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]


4. 解题思路

要求使用时间复杂度为 O(log⁡n) 的算法解决问题,那么就需要使用「二分查找算法」了。

  • 进行两次二分查找,第一次尽量向左搜索。第二次尽量向右搜索。


参考代码

class Solution {public int[] searchRange(int[] nums, int target) {int start = lowerBound(nums, target);if (start == nums.length || nums[start] != target) {return new int[]{-1, -1}; // nums 中没有 target}// 如果 start 存在,那么 end 必定存在int end = lowerBound(nums, target + 1) - 1;return new int[]{start, end};}// lowerBound 返回最小的满足 nums[i] >= target 的 i// 如果数组为空,或者所有数都 < target,则返回 nums.length// 要求 nums 是非递减的,即 nums[i] <= nums[i + 1]private int lowerBound(int[] nums, int target) {int left = 0, right = nums.length - 1; // 闭区间 [left, right]while (left <= right) { // 区间不为空// 循环不变量:// nums[left-1] < target// nums[right+1] >= targetint mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1; // 范围缩小到 [mid+1, right]} else {right = mid - 1; // 范围缩小到 [left, mid-1]}}return left;}
}


关键字:behance网站_黑龙江省建设厅官网_线下推广渠道和方式_推广软文发稿

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: