【leetcode刷题】T12-搜索旋转排序数组II
这是木又陪伴你的第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: trueExample 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 FalseC++版本
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;
}
};【总结】
相关文章：
T9-寻找旋转排序数组中的最小值
T10-寻找旋转排序数组中的最小值II
T11-搜索旋转排序数组
给我好看