网站建设的需要是什么,做网站设计软件,网站首页缩略图 seo,免费网络推广软件有哪些33.搜索旋转排序数组
这是一个非常有趣的问题#xff0c;如果不要求使用O(logn)应该没人会想到吧。。 方法一#xff1a; 极致的分类讨论。旋转排序数组#xff0c;无非就是右边的增区间的数小于左边的增区间的数#xff0c;然后依次排序。因此我们只需要分三类讨论即可… 33.搜索旋转排序数组
这是一个非常有趣的问题如果不要求使用O(logn)应该没人会想到吧。。 方法一 极致的分类讨论。旋转排序数组无非就是右边的增区间的数小于左边的增区间的数然后依次排序。因此我们只需要分三类讨论即可即[left,right]在左增区间[left,right]在右增区间[left,right]在两个区间中间。只有最后一种情况需要讨论更多一点。 前两种情况可以合并为nums[left]nums[right]时的情况这样一定是有序数组。 最后一种情况又分为target在左增区间中target在右增区间中、nums[mid]在左增区间中、nums[mid]在右增区间中一共4种情况。 如果target在左增区间中则有targetnums[right] 如果target在右增区间中则targetnums[right] 如果nums[mid]在左增区间中则有nums[mid]nums[rgiht], 如果nums[mid]在右增区间中则有nums[mid]nums[rgiht], 如果使得rightmid-1;则有target在mid左边则有两种情况 ①mid在右增区间中target小于mid的值 或者 target大于mid的值且大于nums[right]的值即target在左增区间中。 ②mid在左增区间中target小于mid的值 且target也在左增区间中 class Solution {
public:int search(vectorint nums, int target) {int left0,rightnums.size()-1;while(leftright){int mid(leftright)1;if(nums[mid]target) return mid;if(nums[left]nums[0]nums[right]nums[0]){if(nums[mid]target) {rightmid-1;continue;}}else{if(nums[left]nums[0]nums[right]nums[0]){if(nums[mid]target) {rightmid-1;continue;}}else{if(nums[left]nums[0]nums[right]nums[0]){if(nums[mid]nums[right]targetnums[mid]targetnums[right]){rightmid-1;continue;}if(nums[mid]nums[right](targetnums[right]||targetnums[mid])) {rightmid-1;continue;}}}}leftmid1;}return -1;}
};
/*
或者讨论target在哪个区间
if(targetnums[right](targetnums[mid]||nums[mid]nums[right])){rightmid-1;continue;}
if(targetnums[right]targetnums[mid]nums[mid]nums[right]) {rightmid-1;continue;}
*/ 合并情况 class Solution {
public:int search(vectorint nums, int target) {int left0,rightnums.size()-1;while(leftright){int mid(leftright)1;if(nums[mid]target) return mid;if(nums[left]nums[right]){if(nums[mid]target) {rightmid-1;continue;}}else{if(nums[mid]nums[right]targetnums[mid]targetnums[right]) {rightmid-1;continue;}if(nums[mid]nums[right](targetnums[right]||targetnums[mid])) {rightmid-1;continue;}}leftmid1;}return -1;}
}; 方法二 官方思路 一个区间分为左增区间和右增区间那么在任意一个点将这个区间断开分为两个区间一定会有一个区间是顺序区间我们保证每次只在那个顺序区间里找doge如果不在这个顺序区间里我们就直接将指针移入那个区间即可这保证了每一次也是二分的。 class Solution {
public:int search(vectorint nums, int target) {int n (int)nums.size();if (!n) {return -1;}if (n 1) {return nums[0] target ? 0 : -1;}int l 0, r n - 1;while (l r) {int mid (l r) / 2;if (nums[mid] target) return mid;if (nums[l] nums[mid]) {//左区间是顺序区间if (nums[l] target target nums[mid]) {//target在左区间内则rmid-1r mid - 1;} else {l mid 1;}} else {//右区间是顺序区间if (nums[mid] target target nums[n - 1]) {//target在右区间内则lmid1l mid 1;} else {r mid - 1;}}}return -1;}
}; 总结来看二分就是“均分”区间之后判断left移入右边 还是 right移入左边如果可以满足这一性质就是一个二分O(logn)的算法。 不管是第一种方法还是第二种方法都是判断如何移动只是判断方式不同第二种方法更直接。
