摘要：题目要求相比于，中添加了数组中可能存在重复值的条件。这是我们可以将情况分为以下几种。因为如果而且，则左侧或右侧的子数组至少有一个为顺序的数组，这违背题目要求。所哟一定是同理，如果，那么。
题目要求
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Write a function to determine if a given target is in the array. The array may contain duplicates.
相比于I，II中添加了数组中可能存在重复值的条件。大家可以先参考一下我的这篇关于I的博客，在这个基础上，考虑如何实现这道题目。
思路与代码在上一道题目的基础上，我们知道，如果数组中存在重复值，可能会出现类似于[1,3,1,1]这种情况出现。如果在这时候使用二分法，很可能会无法判断出到底属于左半侧数组还是右半侧数组。这是我们可以将情况分为以下几种。
目标值位于左侧上升数组中，也就是说nums[left] 目标值位于右侧上升数组中，也就是说nums[mid] 其它情况 在第三种情况下，我们可以看到该类别满足nums[left]>=nums[mid]且nums[mid]>=nums[right]。这时候，我们可以分析一下， 如果nums[mid]>nums[right]，那么nums[mid]=nums[left]。因为如果nums[mid]>nums[right]而且nums[mid] 同理，如果nums[mid] nums[mid]=nums[left]=nums[right]!=target 代码如下： public boolean search(int[] nums, int target) {
int left = 0 , right = nums.length-1;
while(left<=right){
int mid = ( left + right ) / 2;
if(nums[mid] == target){
return true;
}else if(nums[left] < nums[mid]){
if(target>=nums[left] && target<=nums[mid]){
right = mid-1;
}else{
left = mid + 1;
}
}else if(nums[mid] < nums[right]){
if(target>=nums[mid] && target<=nums[right]){
left = mid + 1;
}else{
right = mid - 1;
}
//判断左右节点是否为目标值，不是则分别调整
}else{
if(nums[left] == target || nums[right] == target){
return true;
}else{
left++;
right--;
}
}
}
return false;
}
简单优化
public boolean search2(int[] nums, int target){
int left = 0 , right = nums.length-1;
while(left<=right){
int mid = ( left + right ) / 2;
if(nums[mid] == target){
return true;
}else if(nums[left] < nums[mid]){
if(target>=nums[left] && target<=nums[mid]){
right = mid-1;
}else{
left = mid + 1;
}
}else if(nums[mid] < nums[right]){
if(target>=nums[mid] && target<=nums[right]){
left = mid + 1;
}else{
right = mid - 1;
}
//精华第三种场景
}else if(nums[mid] > nums[right]){
left = mid + 1;
}else if(nums[mid] < nums[left]){
right = mid - 1;
}else{
left++;
right--;
}
}
return false;
}
想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/67230.html
摘要：如果左边的点比右边的大，说明这两个点之间有一个旋转点，导致了不再有序。因为只有一个旋转点，所以一分为二后，肯定有一半是有序的。 Search in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 mi...
摘要：找中点若起点小于中点，说明左半段没有旋转，否则说明右半段没有旋转。在左右半段分别进行二分法的操作。只判断有无，就容易了。还是用二分法优化 Search in Rotated Sorted Array Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 ...
摘要：这里相比于思路一，更适用于目标节点在中间的情况，而思路一在目标节点分布在数组两侧会效率更高。 题目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 ...
摘要：如正常的升序排列应该是，，，，，，旋转过后可能就是，，，，，，。想法因为这是一个经过旋转的升序数组，我们可以将其看作两个升序的序列，，，和，，。如果在前一个序列，则从前面进行查找。如果在后面一个序列，则从最后一个元素开始查找。 题目详情 Suppose an array sorted in ascending order is rotated at some pivot unknown...
摘要：二分迭代法复杂度时间空间递归栈空间思路找旋转数组的起点，实际上类似找一个山谷，只要两边都比中间高就对了，这和这题很像。 Find Minimum in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 ...
阅读 3380·2023-04-25 16:35
阅读 524·2021-10-11 11:09
阅读 5504·2021-09-22 15:11
阅读 3249·2019-08-30 14:03
阅读 2477·2019-08-29 16:54
阅读 3223·2019-08-29 16:34
阅读 2839·2019-08-29 12:18
阅读 1961·2019-08-28 18:31
