首页 > 代码库 > [LeetCode] Search in Rotated Array II
[LeetCode] Search in Rotated Array II
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
思路：真题思路和http://www.cnblogs.com/vincently/p/4122528.html类似。只是如果有重复的话就不能依靠与边界的比较确定递增的序列。例如，[1,3,1,1,1]，对于A[m]>=A[l]来说，[l,m]的假设就不成立。但是还是可以观察到，左边子数组的值都要大于等于右边子数组的值。将A[m]>=A[l]拆分为两种情况：A[m]>A[l],则区间[l,m]一定递增；如果 A[m]==A[l]确定不了，那就l++，往下看一步。
时间复杂度改变为O(n),空间复杂度O(1)
1 class Solution { 2 public: 3 bool search(int A[], int n, int target) { 4 int first = 0, last = n - 1; 5 while (first <= last) { 6 const int mid = (first + last) / 2; 7 if (A[mid] == target) return true; 8 if (A[first] < A[mid]) { 9 if (A[first] <= target && target < A[mid])10 last = mid - 1;11 else12 first = mid + 1;13 } else if (A[first] > A[mid]){14 if (A[mid] < target && target <= A[last])15 first = mid + 1;16 else 17 last = mid - 1;18 } else {19 first++;20 }21 }22 return false;23 }24 };
[LeetCode] Search in Rotated Array II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。