如何用网页制作网站,沧州网页制作,做羊毛毡的网站,自建网站和第三方平台一、题目描述
给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target#xff0c;返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示…一、题目描述
给你一个按照非递减顺序排列的整数数组 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] 二、题解
思路分析
题目要求我们找到出现target的第一个位置和最后一个位置首先我们想到可以通过暴力枚举的方法来解决该问题即遍历数组并记录target第一次出现和最后一次出现的位置。然而题目要求我们实现时间复杂度为O(log n)的算法且题目中给出的数组为非递减的数组因此我们可以考虑使用二分查找的方法来解决该问题
由于题目中数据量较小使用遍历的方法也可以通过该题
遍历代码
class Solution {public int[] searchRange(int[] nums, int target) {int first -1;int last -1;boolean flg false;//判断是否是第一个位置for (int i 0; i nums.length; i) {//第一个位置if(nums[i] target !flg){first i;flg true;}//最后一个位置//注意处理特殊情况即最后一个元素在最后一个位置时nums[i1]越界if(nums[i] target (i nums.length - 1 || nums[i1] ! target)){last i;}}int[] ret {first,last};return ret;}
} 如何使用二分查找来解决该问题 题目要求我们找到target在数组中第一次出现和最后一次出现的位置利用数组非递减的性质 首先我们查找元素的第一个位置 我们可通过target将数组分为两部分 其中左边部分为小于target的元素右边部分为大于等于target的元素由于右边区域大于等于target因此右边区域最左边的值即为target第一次出现的位置即右边区域的左端点为所求结果 我们定义left指向0位置right指向最后一个元素mid指向中间位置 若mid指向的元素落在右边区间此时nums[mid]大于等于target需要更新right的值由于要找的结果target第一次出现的位置在此区间内即mid所指向的位置可能就是最终结果因此不能将right更新为mid - 1而应更新为mid 若mid所指向的元素落在左边区间此时nums[mid]小于target需要更新 left 的值由于要找的结果不在此区间内因此可将left的结果更新为 mid 1 当left和right之间元素为偶数个时此时中间元素有两个应该选择哪一个作为中间元素 由于我们查找的是右边区间内最左边的元素因此应该选择左边的元素作为中间元素 若选择右边元素作为中间元素能够成功查找到结果吗 当选择右边元素作为中间元素时此时会出现死循环的情况例如 上图中当选择右边元素作为中间元素时mid指向的元素落在右边区间此时将right更新为mid再求mid此时mid仍为指向刚才位置即落在右边区间此时再次更新right为mid再次求mid... 从而死循环 循环条件如何设置 由于我们将right更新为mid因此循环的条件应为left right若循环条件设置为left right当left right时此时找到结果而结果落在右边区间此时会更新right的值而right 更新为mid即当前位置从而死循环 分析完以上问题后我们可以尝试编写查找右边区域最左边元素的代码
//查找target第一次出现的位置(右边区间的左端点)
int left 0,right nums.length - 1,mid left (right - left)/2;
//循环条件应设置为left right
//不能设置为left right否则会死循环
while(left right){//当mid所指向的元素落在左边区间时更新leftif(nums[mid] target){left mid 1;}else{//当mid所指向的元素落在右边区间时此时更新right//由于右边区间的元素大于等于target即结果在该区间内// 因此不能将right更新为mid - 1,而应更新为midright mid;}//更新mid当有两个中间元素时mid应指向其中左边的元素mid left (right - left) / 2;
} 此时我们查找target最后一次出现的位置 与查找第一次出现位置的思路相同我们首先将数组分为两个部分 其中左边区间内元素小于等于target右边区间元素大于target
此时要找的结果即为左边区间的右端点 同样的定义left指向0位置right指向最后一个元素mid指向中间位置 若mid所指向的元素落在左边区间此时需要更新left的值由于要找的结果落在此区间内即mid所指向的位置可能就是最终结果因此不能将left更新为mid 1而应更新为mid 若mid所指向的元素落在右边区间此时需要更新right的值由于要找的结果不在右边区间因此可将right的值更新为mid - 1 当left和right之间元素为偶数个时此时中间元素有两个应该选择哪一个作为中间元素 由于我们查找的是左边区间内最右边的元素因此应该选择右边的元素作为中间元素
即 mid left (right - left 1) / 2;
同样的当选择左边元素作为中间元素时也会造成死循环 此时left的值一直更新为当前位置造成死循环 循环条件的设置 循环条件也同样应该设置为left right否则会死循环
此时我们尝试编写查找左边区间右端点代码
//查找区间右端点
left mid;
right nums.length - 1;
mid left (right - left 1)/2;
while(left right){//当mid所指向的值落在右边区域时更新右端点if(nums[mid] target){right mid - 1;}else{//当mid所指向的值落在左边区域时更新左端点//由于左边区间的元素小于等于target即结果在该区间内//因此不能将left更新为mid 1,而应更新为midleft mid;}//更新mid的值若有两个中间元素时mid应指向其中右边的元素mid left (right - left 1) / 2;
}
完整代码
class Solution {public int[] searchRange(int[] nums, int target) {int[] ret {-1,-1};//若数组为空直接返回retif(nums.length 0){return ret;}//查找target第一次出现的位置(右边区间的左端点)int left 0,right nums.length - 1,mid left (right - left) / 2;//循环条件应设置为left right//不能设置为left right否则会死循环while(left right){//当mid所指向的元素落在左边区间时更新leftif(nums[mid] target){left mid 1;}else{//当mid所指向的元素落在右边区间时此时更新right//由于右边区间的元素大于等于target即结果在该区间内// 因此不能将right更新为mid - 1,而应更新为midright mid;}//更新mid当有两个中间元素时mid应指向其中左边的元素mid left (right - left) / 2;}//此时left right mid,使用哪一个变量进行判断和更新都可以//若数组中无值为target的元素直接返回retif(nums[left] target){ret[0] left;}else{return ret;}//查找区间右端点left mid;right nums.length - 1;mid left (right - left 1)/2;while(left right) {//当mid所指向的值落在右边区域时更新右端点if (nums[mid] target) {right mid - 1;} else {//当mid所指向的值落在左边区域时更新左端点//由于左边区间的元素小于等于target即结果在该区间内//因此不能将left更新为mid 1,而应更新为midleft mid;}//更新mid的值若有两个中间元素时mid应指向其中右边的元素mid left (right - left 1) / 2;}ret[1] left;return ret;}
}
题目来自
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode
