网站建设大概价格,做商城网站的项目背景,深圳机票网站建设,哪个公司的logo品牌设计每天一题#xff0c;防止痴呆题目示例分析思路1题解1#x1f449;️ 力扣原文
题目
给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target#xff0c;返回 [-1,…
每天一题防止痴呆题目示例分析思路1题解1️ 力扣原文
题目
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例
输入nums [5,7,7,8,8,10], target 8
输出[3,4]输入nums [5,7,7,8,8,10], target 6
输出[-1,-1]输入nums [], target 0
输出[-1,-1]分析思路1
1.使用二分查找算法找到元素第一次出现的位置。这里可以用一个变量记录当前找到的最小位置每次找到目标元素时更新这个变量继续在左侧查找直到左侧没有目标元素为止。
2.使用二分查找算法找到元素最后一次出现的位置。这里可以用一个变量记录当前找到的最大位置每次找到目标元素时更新这个变量继续在右侧查找直到右侧没有目标元素为止。 为什么findLef中tint mid left (right - left) / 2; 计算机中整数的表示是有限的如果两个很大的整数相加可能会导致结果超出整数类型的表示范围发生整数溢出。例如如果 left 和 right 都很大它们的和可能会超出 int 类型的最大值导致结果变成负数或者其他的不正确的结果。因此在计算中间位置时如果直接采用 (right left) / 2 的方法来计算中间位置可能会导致整数溢出的问题。而采用 (right - left) / 2 的方法来计算中间位置则可以避免这个问题的出现因为 right 和 left 的差值不会超过 int 类型的表示范围所以计算结果也不会超出 int 类型的范围。 为什么findRight中int mid left (right - left 1) / 2; 这是因为在二分查找中当左右边界相邻时如果中间位置的计算公式为 int mid left (right - left) / 2;那么会出现死循环的情况。因为此时 left 和 right 都指向同一个位置而中间位置的计算公式为 (left right) / 2会一直得到这个位置而不会结束循环。 为了避免这种情况我们可以将计算中间位置的公式修改为 int mid left (right - left 1) / 2;这样在左右边界相邻时中间位置会取右边界的位置从而结束循环。 题解1
class Solution {public int[] searchRange(int[] nums, int target) {int[] result new int[]{-1, -1};if (nums null || nums.length 0) {return result;}int left 0, right nums.length - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {result[0] findLeft(nums, target, left, mid);result[1] findRight(nums, target, mid, right);break;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return result;}private int findLeft(int[] nums, int target, int left, int right) {while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {right mid;} else {left mid 1;}}return nums[left] target ? left : -1;}private int findRight(int[] nums, int target, int left, int right) {while (left right) {int mid left (right - left 1) / 2;if (nums[mid] target) {left mid;} else {right mid - 1;}}return nums[left] target ? left : -1;}}执行结果
