网站建设需要了解的,快速排名软件哪个好,行业类网站模板,美橙域名查询网站解题思路#xff1a; 1.获取信息#xff1a; 一个数组是按升序排列的#xff0c;并且没有重复的元素 现在任意找出一个下标#xff0c;将下标后面的元素及下标元素和前面的元素整体换个位置 如#xff1a;[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 要…解题思路 1.获取信息 一个数组是按升序排列的并且没有重复的元素 现在任意找出一个下标将下标后面的元素及下标元素和前面的元素整体换个位置 如[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 要求现在给出了一个旋转后的数组和一个整数判断整数在不在这个数组中如果在就返回下标如果不在就返回-1 限制条件要求时间复杂度为O(log n) 其他条件可以看一下题目下面的提示这里就不一一列举 2.分析题目 看见这个时间复杂度我就想到了二分查找法那么该怎么用这个方法来解这道题呢 我想了两种方式分别会在下面的方法中借着代码逐一讲解在此之前你可以自己先想一想 3.示例查验无 4.尝试编写代码 1二分查找法 I 思路这道题如果想变得更简单的话我想那一定是知道了这个数组从哪里开始旋转的那么我们可以找到这个旋转的点吗 当然可以我们取数组第一个元素作为参照对整个数组进行二分查找 先初始化begin0 , endnums.size()-1 再循环直到beginend 每次取中点mid与数组第一个元素相比较就会出现两种情况默认它们不相等 1.mid大于数组第一个元素 我们就取mid右边的区间继续循环因为旋转点一定在右边的区间内 2.mid小于数组第一个元素 我们就取mid左边的区间继续循环因为旋转点一定在左边的区间内 当循环完后此时begin就是旋转点 那么下面就只需要确定在begin左边还是右边的区间取目标值了那么怎么确定呢 只需要比较数组第一个元素和目标值的大小即可无非就两种情况默认它们不相等 1.数组第一个元素大于目标值说明目标值在begin的右区间 2.数组第一个元素小于目标值说明目标值在begin的左区间 接下来只需要常规的二分法查找目标值即可
以下是完整代码
class Solution {
public:int search(vectorint nums, int target) {int numnums[0];//取数组第一个元素int sizenums.size()-1;//取数组的大小if(targetnums[size]||targetnums[0])return targetnums[0]?0:size;//如果队首或队尾是目标值就返回答案int begin0,endsize;//要开始二分咯这里是查找旋转点while(beginend){int mid(beginend)/2;if(nums[mid]target)return mid;if(numnums[mid])beginmid1;else endmid;}//此时begin就是旋转点了if(nums[begin]target)return begin;//如果旋转点就是目标值就返回答案if(begin0||beginsize){//特殊情况如果旋转点在队首或队尾那么相当于数组是一个升序数组没有进行旋转就直接进行常规的二分查找法int newbegin0,newendsize;while(newbeginnewend){int mid(newbeginnewend)/2;if(nums[mid]target)return mid;else if(nums[mid]target)newendmid;else newbeginmid1;}if(nums[newbegin]target)return newbegin;return -1;}//以下是旋转点不在队首或队尾的情况if(nums[begin]target)return -1;//如果目标值小于转折点对应的那个元素该元素是数组的最小值else if(nums[begin]target){//如果目标值大于转折点对应的那个元素if(targetnum)return 0;if(targetnum){begin--; int newbegin0,newendbegin;while(newbeginnewend){int mid(newbeginnewend)/2;if(nums[mid]target)return mid;else if(nums[mid]target)newendmid;else newbeginmid1;}if(nums[newbegin]target)return newbegin;}else{int newbeginbegin,newendsize;while(newbeginnewend){int mid(newbeginnewend)/2;if(nums[mid]target)return mid;else if(nums[mid]target)newendmid;else newbeginmid1;}if(nums[newbegin]target)return newbegin;}}return -1;}
}; (2)二分查找法II 思路我们可以不可以不用找出旋转点直接使用二分法来做这道题呢 当然可以我们直接使用二分查找法取到了一个中点对吧 那么这个中点将这个数组一分为二成了两个区间我们知道其中一个区间一定是升序排列另一个区间就不一定是了 那么我们可以根据目标值的大小来确定它是在哪个区间 如果实在那个升序的区间就可以使用二分查找法来直接查找到结果了 如果不再那个升序的区间那么此时这个区间 我们可以把它看成是一个新的数组并且这个数组是不是也是有一个旋转点 这么一看此时就又回到了原点就可以重复上述操作直到找到结果
class Solution {
public:int search(vectorint nums, int target) {int sizenums.size();//数组的大小int l0,rsize-1;//要开始二分查找法了while(lr){int mid(lr)/2;if(nums[mid]target)return mid;if(nums[0]nums[mid]){if(targetnums[0]targetnums[mid])rmid;else{lmid1;}}else{if(targetnums[size-1]targetnums[mid])lmid1;else{rmid-1;}}}return nums[l]target?l:-1;}
};
以上就是本次题解的全部内容了
做一道题不要只看题解要自己再动手写一下才会真正地得心应手知道吗
纸上得来终觉浅绝知此事要躬行
