seo优化软件哪个好_重庆政府服务网_网络营销教学大纲_网上营销型网站

目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析

---

一、问题描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

二、解题思路

• 二分查找 是解决这种时间复杂度要求的最优选择。
• 我们需要找到目标值 target 在数组中的最左边界和最右边界。
• 为了在 O(log⁡n)O(\log n)O(logn) 的时间复杂度内实现这个任务，我们可以两次使用二分查找：
  • 第一次查找 target 的左边界。
  • 第二次查找 target 的右边界。

详细步骤：

• 查找左边界：

  • 使用二分查找，找到 target 出现的最左边的索引位置。如果中间值 nums[mid] 大于或等于 target，则移动 right；否则移动 left，直到找到 target 的最左边界。

• 查找右边界：

  • 类似地，我们使用二分查找找到 target 的最右边的索引位置。如果中间值 nums[mid] 大于 target，则移动 right；如果中间值小于等于 target，则移动 left，直到找到 target 的最右边界。

• 如果数组中不存在 target，直接返回 [-1, -1]。

三、代码

class Solution {public int[] searchRange(int[] nums, int target) {int[] result = new int[2];result[0] = findLeft(nums, target);result[1] = findRight(nums, target);return result;}// 查找左边界private int findLeft(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}// 检查 left 是否越界且是否是目标值if (left < nums.length && nums[left] == target) {return left;}return -1;}// 查找右边界private int findRight(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;} else {right = mid - 1;}}// 检查 right 是否越界且是否是目标值if (right >= 0 && nums[right] == target) {return right;}return -1;}
}

四、复杂度分析

• 时间复杂度：O(log⁡n)O(\log n)O(logn)。每次二分查找都会将搜索空间减半，因此两个二分查找总的时间复杂度是 O(log⁡n)O(\log n)O(logn)。
• 空间复杂度：O(1)O(1)O(1)。我们只使用了常数空间来存储边界和结果数组。