这是木又陪伴你的第19天
今天分享leetcode第12篇文章,也是leetcode第81题—搜索旋转排序数组II(Search in Rotated Sorted Array II),地址是:https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
【英文题目】(学习英语的同时,更能理解题意哟~)
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6]
might become [2,5,6,0,0,1,2]
).
You are given a target value to search. If found in the array return true
, otherwise return false
.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
【中文题目】
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,0,1,2,2,5,6]
可能变为 [2,5,6,0,0,1,2]
)。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true
,否则返回 false
。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
【思路】
参考「T11-搜索旋转排序数组」,我们同样使用二分查找的变形方法:l->mid和mid->r两个区间总有一个是有序的,每次总能选择一个区间继续进行搜索。nums[mid] < nums[r]时,mid -> r区间有序,若nums[mid] < target <= nums[r],则选择mid -> r区间,反之选择l -> mid区间;nums[mid] > nums[r]时,l -> mid区间有序,若nums[l] <= target < nums[mid],则选择l -> mid区间,反之选择 mid -> r 区间。
但是存在重复元素,很可能存在nums[mid] == nums[r]的情况,这样我们就不知道到底mid -> r区间还是l -> mid区间是有序的。
换个思路,我们是不是可以比较nums[mid]和nums[r-1]的大小关系呢?
这样是可行的,一直类推,直到nums[mid] != nums[r]或者r == mid,就可以确定到底是选择哪个区间继续进行搜索。
这样,平均时间复杂度为O(log n),最坏情况时间复杂度为O(n)(所有元素都一样时)
(当然,最简单的方法还是暴力破解,时间复杂度为O(n))
【代码】
python版本
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return True
# 忽略mid右边所有nums[mid]值
while (r > mid) and (nums[mid] == nums[r]):
r -= 1
# 如果nums[mid] == nums[r],说明mid == r,应该使得r=mid-1
if nums[mid] <= nums[r]:
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
else:
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
return False
C++版本
class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l <= r){
int mid = (l + r) / 2;
if(nums[mid] == target)
return true;
// 忽略mid右边所有nums[mid]值
while(r > mid && nums[mid] == nums[r])
r--;
// 如果nums[mid] == nums[r],说明mid == r,应该使得r=mid-1
if(nums[mid] <= nums[r]){
if(nums[mid] < target && target <= nums[r])
l = mid + 1;
else
r = mid - 1;
}else{
if(nums[l] <= target && target < nums[mid])
r = mid - 1;
else
l = mid + 1;
}
}
return false;
}
};
【总结】
相关文章:
给我好看