看题:
题目很容易看明白,无非就是查找数组最小值,而无论他旋转多少次,其实都等于在固定点旋转一次就可以实现输入数组,可以直接遍历数组查找最小值,但显然这样时间复杂度为O(N),而我们采用二分法则会使得复杂度降到O(logN)
class Solution {
public:
int findMin(vector<int>& nums) {
int len=nums.size();
if(!len||len==1)return nums[0];
if(nums[0]<nums[len-1])return nums[0];//防止一开始就是一个有序数组这样进入下列循环可能导致旋转点判断在数组末尾
int left=0,right=len-1;
while(left<right){
int mid=(left+right)/2;
if(nums[0]<=nums[mid]){
left=mid+1;
}
else{
right=mid;
}
}
return nums[left];
}
};
进一步应用,查找旋转后的数组中某一个目标值:
方法一:先找出旋转点,在判断目标值所在区间,然后在有序区间内查找目标值
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size(), mid = 0;
while (left < right)
{
mid = (left + right) / 2;
if (nums[0] > nums[mid]) right = mid; //找出旋转点
else left = mid + 1;
}
if (target < nums[0]) right = nums.size(); //判断target在旋转点左边区间还是右边区间
else left = 0;
while (left < right)
{
mid = (left + right) / 2;
if (nums[mid] == target) return mid; //继续在有序的子区间找出目标下标
else if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid;
}
return -1;
}
};
方法二:将数组一分为二,其中一定有一个是有序的,另一个可能是有序,也能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二,其中一个一定有序,另一个可能有序,可能无序。就这样循环.
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
int p1 = 0, p2 = nums.size() - 1;
int mid = p1;
while (p1 <= p2)
{
mid = (p1 + p2) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] >= nums[p1]) // 说明[p1,mid]区间是有序的
{
// 因为[p1,mid]区间是有序的,所以通过p1和mid处的值就能判断target在不在区间内
if (nums[p1] <= target && target < nums[mid]) p2 = mid - 1;
else p1 = mid + 1; // 如果不在,就去[mid+1,p2]区间找target
}
else // 说明[mid,p2]区间是有序的
{
// 因为[mid,p2]区间是有序的,所以通过mid和p2处的值就能判断target在不在区间内
if (nums[mid] < target && target <= nums[p2]) p1 = mid + 1;
else p2 = mid - 1; // 如果不在,就去[p1,mid-1]区间找target
}
}
return -1;
}
};
进阶:查找含有重复元素的数组时,我们会遇到一种情况:
nums[left] = nums[mid] 和nums[mid] = nums[right],同时成立,例如:旋转后数组为[1,0,1,1,1]此时没办法判断那个区间有序,那个区间无序,所以此时要使得left++,right–,区间缩小在进行判断
class Solution {
public:
bool search(vector<int>& nums, int target) {//有重复元素时
int len = nums.size();
if (!len)return false;
int left = 0, right = len - 1;
while (left <= right) {
int mid = (right + left) / 2;
if (target == nums[mid])return true;
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
left++;
right--;
}
else if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
else {
if (target <= nums[right] && target > nums[mid]) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
}
return false;
}
};
这些日子一直在简书上使用markdown写作,已经渐渐的痴迷于这种简洁纯粹的写作方...
本文实例讲述了正则表达式中的操作符及说明。分享给大家供大家参考,具体如下: ...
从另一台机器上复制过来的项目,由于两台机器的库目录不一致,导致了stdio.h等很...
3月22日消息 外媒 Winfuture 报道,此前微软面向 Insider 预览用户公布了 Window...
2月23日消息 据外媒 Windows Latest 今日报道,借助 Windows 10 Sun Valley 更新...
Go原生就支持连接数据库,所以在使用 Golang 开发时,当需要数据库交互时,即可...
Greediness(贪婪型):最大匹配 X、X*、X+、X{n,} 是最大匹配。例如你要用 “....
橡皮擦一个逗趣的互联网高级网虫。 观前提醒本篇文章涉及知识点巨大建议先收藏再...
ajax 实现三级联动,相当于写了一个小插件,用的时候直接拿过来用就可以了,这里...
1 . 目标 演示下图的git reset 各选项的效果。 2. Git Reset操作说明 图中说明:...