描述
Follow up for "Search in Rotated Sorted Array":What if duplicates are allowed?Would this affect the run-time complexity? How and why?Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
分析 允許重復元素，則上一題中如果 A[m]>=A[l], 那么 [l,m] 為遞增序列的假設就不能成立了，比 如 [1,3,1,1,1]。 如果 A[m]>=A[l] 不能確定遞增，那就把它拆分成兩個條件: ? 若 A[m]>A[l]，則區間 [l,m] 一定遞增 ? 若 A[m]==A[l] 確定不了，那就 l++，往下看一步即可。
代碼
class Solution {public: bool search(vector<int>& nums, int target) { int first = 0; int last = nums.size(); while (first != last) { int mid = (first + last) / 2; if (nums[mid] == target) return true; if (nums[first] < nums[mid]) { if (nums[first] <= target && target < nums[mid]) last = mid; else first = mid + 1; } else if (nums[first] > nums[mid]) { if (nums[mid] < target && target <= nums[last - 1]) first = mid + 1; else last = mid; } else ++first; // skip duplicate one } return false; }};新聞熱點
疑難解答
