[LeetCode每日一题]81. 搜索旋转排序数组 II
2024-10-19 08:26:13
[LeetCode每日一题]81. 搜索旋转排序数组 II
问题
已知存在一个按非降序排列的整数数组 nums ,数组中的值不必互不相同。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ,则返回 true ,否则返回 false 。
示例 1:
输入:nums = [2,5,6,0,0,1,2], target = 0
输出:true
示例 2:
输入:nums = [2,5,6,0,0,1,2], target = 3
输出:false
提示:
1 <= nums.length <= 5000
-10的四次方 <= nums[i] <= 10的四次方
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10的四次方 <= target <= 10的四次方
大水题……
思路及代码
class Solution {
public:
bool search(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); i++)
if (nums[i] == target)
return true;
return false;
}
};
既然题解说要用二分,那就用二分法试试看吧
这题相较于常规的二分,不同点在于它是部分非单调递减有序的(后面的有序都是指非单调递减有序),这也意味着[l, mid]和[mid,r]至少有一个区间是有序的。我们通过这个有序的区间来判断target在不在这个区间的里面(无序区间是不好判断在不在里面的),如果在,那就在有序的区间里面找(剪掉了另外一部分,这也是二分的实质——减治),不在的话,就是另外一个区间里面找(也是剪掉了一部分)
还要注意一个特殊情况,就是重复元素带来的nums[l] == nums[mid] && nums[mid] == nums[r],这会导致无法判断区间 [l,mid] 和区间 [mid+1,r] 哪个是有序的。例如 nums=[3,1,2,3,3,3,3],target=2,首次二分时判断区间 [0,3] 是有序的,然后确定target在不在这里面的时候就出错了。
对于这种情况,我们只能将当前二分区间的左边界加一,右边界减一,然后在新区间上继续二分查找。
class Solution {
public:
bool search(vector<int>& nums, int target) {
int n = nums.size();
int l = 0, r = n - 1, mid;
while (l <= r) {
mid = (l + r) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[l] == nums[mid] && nums[mid] == nums[r]) { //防止特殊情况
l++;
r--;
} else if (nums[l] <= nums[mid]) { //左边是不是非单调递减有序的?
if (nums[l] <= target && target < nums[mid]) { //是的话,target在不在左边?
r = mid - 1;//在左边
} else {
l = mid + 1;//在右边
}
} else { //如果左边不是单调递减有序的话,那右边一定是
if (nums[mid] < target && target <= nums[r]) { //在不在右边?
l = mid + 1;//在右边
} else {
r = mid - 1;//不在右边
}
}
}
return false;
}
};
最新文章
- 简析TCP的三次握手与四次分手
- Net设计模式实例之单例模式( Singleton Pattern)
- Memcache教程 Memcache零基础教程
- iOS学习之cocoaPods
- mvc之文件下载
- wpf 线程
- Linux服务器中木马(肉鸡)手工清除方法
- 【五子棋AI循序渐进】——多线程搜索
- iOS5中UIViewController的新方法
- NWR协议
- WCF学习笔记(1)——Hello WCF
- 解决ie8不兼容jquery trim问题
- 【转】LINUX下一款不错的网站压力测试工具webbench
- ThinkPHP快捷函数
- css3制作一个漂亮的按钮
- 浅谈SQL优化入门:1、SQL查询语句的执行顺序
- php中trait的使用
- Angular changeDetction
- Kaldi阅读并更改代码
- Win10系列:JavaScript综合实例2