LEETCODE 34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]
。
示例 1:
输入: nums = [5,7,7,8,8,10]
, target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10]
, target = 6
输出: [-1,-1]
题解
如果修改下题目要求,不要求返回给定值
的第一个(开始位置)、最后一个(结束位置),只要等于给定的值就返回,那会变成什么样呢?
假设给定的数组如下图所示,给定的值是3
,求下标。
上图的数组中下标2
,3
,4
,5
,6
都满足要求,返回任意一个都可以了。
这个查找过程用正常的二分查找就可以满足:
def binary_search(nums): if not nums: return -1 begin = 0 end = len(nums)-1 while begin<=end: mid = begin+(end-begin)//2 if nums[mid]>target: end = mid-1 elif nums[mid]<target: begin = mid+1 else: return mid return -1
如果对二分查找没有印象了,可以参考这篇文章回忆一下。
现在我们再把题目的要求加上,已经定位到3
这个元素了,如果求得第一个
3和最后一个
3出现的位置呢?
如果直接挨个向前移动查找,或者挨个向后移动查找是不行的。
题目要求了时间复杂度是O(logN),挨个查找的话,时间复杂度就变成O(N)了,而且这么查找的话,跟从头到尾扫描一遍也没区别,那么就必须用更高的效率找到第一个和最后一个元素。
到这里,我们就有一个大致的脉络了
-
首先用正常的二分查找定位到给定的元素,时间复杂度O(logN) -
在定位到指定元素的情况下,用O(logN)时间复杂度查找第一个/最后一个
第一点题我们已经解决了,现在看看如何解决第二点。
怎么样才算找到第一个
目标值呢?
很简单,当nums[i]
等于nums[i-1]
时,说明nums[i]
肯定不是第一个,那么继续缩小右边界,往左边查找。直到不满足条件时,此时就找到了第一个给定值。
但还有一个特殊情况,nums[i]
的下标为0
时,这也很好理解,前面都没元素了,那当前元素肯定就是第一个了。
对于最后一个元素也是类似的
如果nums[i]
等于nums[i+1]
就增大左边界,往右边查找,直到不满足条件,此时就找到了最后一个给定值。
如果nums[i]
的下标是len(nums)-1
,那也不用找了。
至此,我们就实现了完整的查找逻辑了
def binary_search(nums): if not nums: return -1 begin = 0 end = len(nums)-1 while begin<=end: mid = begin+(end-begin)//2 if nums[mid]>target: end = mid-1 elif nums[mid]<target: begin = mid+1 else: # 找到目标值了,开始查找第一个目标值 if mid>0 and nums[mid]==nums[mid-1]: end = mid-1 else: return mid return -1
详细说明下上面代码中else
中的这段:
if mid>0 and nums[mid]==nums[mid-1]:
end = mid-1
else:
return mid
既然找到了目标值,就将当前值和前一个值对比,如果一样说明没找到,那么就需要缩小右边界。
缩小右边界的原因是我们要找第一个
,第一个肯定是在最左边,所以就要缩小右边界。
下面演示查找第一个
目标值的过程(目标值是3):
接着是查找最后一个
目标值的过程(目标值是3):
java代码:
class Solution { public int[] searchRange(int[] nums, int target) { if(nums==null) { return new int[]{-1,-1}; } int firstIndex = find(true,nums,target); int lastIndex = find(false,nums,target); return new int[]{firstIndex,lastIndex}; } //查找第一个和最后一个元素 private int find(boolean isFindFirst,int[] nums,int target) { int begin = 0; int end = nums.length-1; //if和else if的逻辑跟正常的二分查找一样 while(begin<=end) { int mid = begin+(end-begin)/2; if(nums[mid]>target) { end = mid-1; } else if(nums[mid]<target) { begin = mid+1; } //找到目标值了,开始定位到第一个和最后一个位置 else { //查找第一个和最后一个逻辑很类似,这里用一个变量标记 //是查找第一个还是查找最后一个 if(isFindFirst) { //如果不满足条件,缩小右边界,继续往左边查找 if(mid>0 && nums[mid]==nums[mid-1]) { end = mid-1; } else { return mid; } } else { //如果不满足条件,增大左边界,继续往右边查找 if(mid<nums.length-1 && nums[mid]==nums[mid+1]) { begin = mid+1; } else { return mid; } } } } return -1; } }
python代码:
class Solution(object): def searchRange(self, nums, target): if not nums: return [-1,-1] n = len(nums) # 查找第一个和最后一个元素 def find(is_find_first): begin = 0 end = n-1 # if和elif的逻辑跟正常的二分查找一样 while begin<=end: mid = begin+(end-begin)/2 if nums[mid]>target: end = mid-1 elif nums[mid]<target: begin = mid+1 # 找到目标值了,开始定位到第一个和最后一个位置 else: # 查找第一个和最后一个逻辑很类似,这里用一个变量标记 # 是查找第一个还是查找最后一个 if is_find_first: # 如果不满足条件,缩小右边界,继续往左边查找 if mid>0 and nums[mid]==nums[mid-1]: end = mid-1 else: return mid else: # 如果不满足条件,增大左边界,继续往右边查找 if mid<n-1 and nums[mid]==nums[mid+1]: begin = mid+1 else: return mid return -1 return [find(True), find(False)]
(全文完)
20 次阅读