leetCode-81-Search-in-Rotated-Sorted-ArrayII
题目描述(中等难度)
“>33 题解法三的基础上去修改。33 题算法基于一个事实,数组从任意位置劈开后,至少有一半是有序的,什么意思呢?
比如 [ 4 5 6 7 1 2 3] ,从 7 劈开,左边是 [ 4 5 6 7] 右边是 [ 7 1 2 3],左边是有序的。
基于这个事实。
我们可以先找到哪一段是有序的 (只要判断端点即可),知道了哪一段有序,我们只需要用正常的二分法就够了,只需要看 target 在不在这一段里,如果在,那么就把另一半丢弃。如果不在,那么就把这一段丢弃。
public int search(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (target == nums[mid]) {
return mid;
}
//左半段是有序的
if (nums[start] <= nums[mid]) {
//target 在这段里
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1;
//target 在另一段里
} else {
start = mid + 1;
}
//右半段是有序的
} else {
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
如果不加修改,直接放到 leetcode 上跑,发现 nums = [ 1, 3, 1, 1, 1 ] ,target = 3,返回了 false,当然是不对的了。原因就出现在了,我们在判断哪段有序的时候,当 nums [ start ] <= nums [ mid ] 是认为左半段有序。而由于这道题出现了重复数字,此时的 nums [ start ] = 1, nums [ mid ] = 1,但此时左半段 [ 1, 3, 1 ] 并不是有序的,所以造成我们的算法错误。
所以 nums[start] == nums[mid] 需要我们单独考虑了。操作也很简单,参考[这里](<https://leetcode.com/problems/search-in-rotated-sorted-array-ii/discuss/28218/My-8ms-C%2B%2B-solution-(o(logn)-on-average-o(n)-worst-case),当相等的时候,我们只需要让 start++ 就够了。
public boolean search(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (target == nums[mid]) {
return true;
}
//左半段有序
if (nums[start] < nums[mid]) {
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else if(nums[start] == nums[mid]){
start++;
//右半段有序
}else{
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return false;
}
时间复杂度:最好的情况,如果没有遇到 nums [ start ] == nums [ mid ],还是 O(log(n))。当然最差的情况,如果是类似于这种 [ 1, 1, 1, 1, 2, 1 ] ,target = 2,就是 O ( n ) 了。
空间复杂度:O ( 1 )。
总
基于之前的算法,找出问题所在,然后思考解决方案。开始自己一直纠结于怎么保持时间复杂度还是 log ( n ),也没想出解决方案,看了 discuss,发现似乎只能权衡一下。另外 阅读全文
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程
![JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。](https://static.javajike.com/img/common/wx-fzp.png)
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com