题目:
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [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
解题思路:
虽然题目没说,但是应该就像 搜索旋转排序数组(也就是上一篇随笔,以下简称“无重复”) 那样的时间复杂度要求O(logn)的。
这里所不同的是有重复数字的出现,若是用无重复那样的思路的话,必须得处理好两边和中间数相等的情况,例如{1,3,1,1,1},中间是1,两边也是1,用无重复那样的判断就会误判。为解决以上问题,我们再来看一遍题目,这题的返回内容不是下标,而是true或者false,那我们试想一下若是把例中重复多余的1去掉,也不会影响我们的输出。并且此时我们就可以用无重复那样的方式去二分了。
代码:
1 class Solution { 2 public: 3 bool search(vector<int>& nums, int target) { 4 int left = 0; 5 int right = nums.size() - 1; 6 while(left <= right) { 7 while(left < right && nums[left] == nums[left+1]) ++left; //去除重复多余的数 8 while(left < right && nums[right] == nums[right-1]) --right; 9 int mid = (left + right)/2; 10 if(nums[mid] == target) { 11 return true; 12 } 13 if(nums[mid] < nums[right]) { 14 if(nums[mid] < target && nums[right] >= target) 15 left = mid + 1; 16 else 17 right = mid - 1; 18 } 19 else { 20 if(nums[mid] > target && nums[left] <= target) 21 right = mid - 1; 22 else 23 left = mid + 1; 24 } 25 } 26 return false; 27 } 28 };