本文主要是介绍*Leetcode 81. Search in Rotated Sorted Array II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
常规容易想到的解法：
基本就是两点：1、判断在两个上升的段的哪个段 2、mid跟r相等的时候r--可以解决问题的
class Solution {
public:bool search(vector<int>& nums, int target) {if(nums.size() == 0) return false;int l = 0, r = nums.size()-1;//int end = nums.size() - 1;while (l <= r) {int mid = (l + r)/2;if (target == nums[r] || target == nums[mid]) return true;if (nums[mid] == nums[r]) {// for (int j = l; j <= r; j ++) {// if (nums[j] == target) return true;// } // return false;r --;continue;}if (nums[mid] > nums[r]) {if (target < nums[mid]) {if (target > nums[r]) {r = mid - 1;} else {l = mid + 1; }} else {l = mid + 1;}} else {if (target < nums[mid]) {r = mid - 1 ;} else {// target > nums[mid]if (target > nums[r]) {r = mid - 1;} else {l = mid + 1;}}} }return false;}};
看到的最好的解法:
class Solution {
public:bool search(vector<int>& nums, int target) {int left = 0, right = nums.size()-1, mid;while(left<=right){mid = (left + right) >> 1;if(nums[mid] == target) return true;// the only difference from the first one, trickly case, just updat left and rightif( (nums[left] == nums[mid]) && (nums[right] == nums[mid]) ) {++left; --right;}else if(nums[left] <= nums[mid]){if( (nums[left]<=target) && (nums[mid] > target) ) right = mid-1;else left = mid + 1; }else{if((nums[mid] < target) && (nums[right] >= target) ) left = mid+1;else right = mid-1;}}return false;}
};这篇关于*Leetcode 81. Search in Rotated Sorted Array II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
