> 文章列表 > 33. 搜索旋转排序数组

33. 搜索旋转排序数组

33. 搜索旋转排序数组

整数数组 nums 按升序排列,数组中的值 互不相同 。

在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4

示例 2:

输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1

示例 3:

输入:nums = [1], target = 0
输出:-1

提示:

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

这道题目乍一看不难,给他遍历一遍不久行了吗?
但是题目有个要求,时间复杂度为O(log n),那遍历的办法就不行了。
那怎么样才能达到O(log n)呢?

看这个题的要素:数组,查找。应该想到二分查找这个办法(想不到的再去复习复习)。

二分查找简单,但是这个题之所以是中等难度而不是简单,就在于它是个旋转数组。

虽然看起来很唬人,但是仔细分析就能发现,旋转之后,数组的一半总是有序上升,一半还是旋转数组。(想不明白可以在纸上写一写,很容易发现规律)

发现规律之后就很简单了,我们可以在有序的一半执行二分查找,在另一半执行递归或者迭代,因为另一半的数组形式跟原数组是一样的嘛。

代码:

class Solution {
private://二分查找int searchAscend(vector<int>& nums, int left, int right, int target){int res = -1;//当target不在查找范围内,返回-1if(target<nums[left] || target>nums[right])return res;else{while(left<=right){int mid = left+(right-left)/2;if(target==nums[mid]){res = mid;break;}else if(target>nums[mid]){left=mid+1;}else if(target<nums[mid]){right=mid-1;}}}return res;}//递归调用,因为旋转之后,必有半边是有序升,有半边是跟原数组一样旋转形状int searchRevolve(vector<int>& nums, int left, int right, int target){int mid = left+(right-left)/2;int res = -1;/*剪枝:1.当target == nums[mid]时返回;2.当target != nums[mid]且left == right,即数组只有一个元素时,返回-1;3.当target != nums[mid]且mid == left,即数组只有两个元素时,判断target == nums[right],相等返回right,否则返回-1;*/if(target == nums[mid]) return mid;else if(left == right) return res;else if(mid == left){if(target == nums[right]) return right;else return res;}//当左半边时升序时if(nums[left] < nums[mid]){//左半边调用二分查找res = searchAscend(nums, left, mid-1, target);if(res!=-1) return res;else{//右半边递归调用res = searchRevolve(nums, mid+1, right, target);}}//当右半边时升序时else if(nums[mid] < nums[right]){//右半边二分查找res = searchAscend(nums, mid+1, right, target);if(res!=-1) return res;else{//左半边递归调用res = searchRevolve(nums, left, mid-1, target);}}return res;}
public:int search(vector<int>& nums, int target) {if(nums.size()==1){return nums[0]==target?0:-1;}int left=0, right=nums.size()-1;return searchRevolve(nums, left, right, target);}
};

我的代码看起来挺复杂,思路其实简单。

ac之后看了看评论区的大佬们,发现果然有很牛逼的写法
极简 Solution