首页 > 代码库 > leetcode[81] Search in Rotated Sorted Array II
leetcode[81] Search in Rotated Sorted Array II
此题是Search in Rotated Sorted Array的加强版，将一个有序数组往右移动若干位。这里的有序数组允许有重复数字。
如果没有重复数字，那么复杂度是O(logn)，用二分查找，根据中间值和左右两边的大小，以及和target的大小，来判断缩小一半查找。
但是出现重复数字之后，如果中间值和左右两边的值相等，我们就不知道如何切除一半了，这时候就只能将边界缩小，也就是左边界加一，或者右边界减一。但是这个复杂度就是O(n)了
class Solution {public: bool search(int A[], int n, int target) { if (n == 0) return false; int left = 0, right = n-1; while(left <= right) { int mid = (left + right)/2; if (A[mid] == target || A[left] == target || A[right] == target) return true; if (A[mid] > A[left]) { if (A[mid] > target && A[left] < target) { right = mid - 1; } else { left = mid + 1; } } else if (A[mid] < A[left]) { if (A[mid] < target && A[right] > target) { left = mid + 1; } else { right = mid - 1; } } else left++; } return false; }};
我在做的过程中还想到要判断的一个是，当左边等于中间，但是中间不等于右边的时候，那么可以缩短一半，同理，如果右边的等于中间，但是左边的不等于中间的时候也可以缩短一半。只有当左右两边和中间都相等的时候才不知道如何判断。右边减一或者左边加一。
class Solution {public: bool search(int A[], int n, int target) { if (n == 0) return false; int left = 0, right = n-1; while(left <= right) { int mid = (left + right)/2; if (A[mid] == target || A[left] == target || A[right] == target) return true; if (A[mid] == A[left] && A[mid] == A[right]) {right--; continue;} if (A[mid] == A[left]) { left = mid + 1;} if (A[mid] == A[right]) { right = mid - 1;} if (A[mid] > A[left]) { if (A[mid] > target && A[left] < target) { right = mid - 1; } else { left = mid + 1; } } else { if (A[mid] < target && A[right] > target) { left = mid + 1; } else { right = mid - 1; } } } return false; }};
leetcode[81] Search in Rotated Sorted Array II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。