每天一道leetcode-81
前言
目前准备每天刷一道题leetcode的题目，以此来激励那些零基础入门的人，千万不要被什么科班和非科班的说法吓倒了，计算机这个行业只要你肯努力，没有什么逾越不了的鸿沟。
只要你肯努力，一份努力，一份汗水，在程序员这个职业，你的每一份付出都会得到对应的那一份汇报，尊重学习规律，循序渐进，别想着一口吃个胖子，罗马也不是一天建成的，有朝一日，你终会变成你想成为的人。
题目目前可能需要一定的算法与数据结构基础才能看懂，后序会写一下零基础也能看懂的入门知识，然后就可以看懂我编写的题目了~
案例
题目
leetcode-81 在有重复数字的有序数组中寻找n
tag(分类）: 二分查找这一类
链接：
https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
题目详述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 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进阶:
- 这是 搜索旋转排序数组 的延伸题目，本题中的
nums可能包含重复元素。 - 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
题解
先上代码~
class Solution {
public boolean search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right)
{
int mid = left + (right-left)/2;
if(nums[mid] == target || nums[left] == target || target == nums[right])
return true;
if(nums[mid] > nums[left])
{
if(target > nums[mid])
left = mid + 1;
else{
if(target > nums[left])
right = mid - 1;
else
left = mid + 1;
}
}else if(nums[mid] < nums[left])
{
if(target < nums[mid])
right = mid -1;
else{
if(target > nums[left])
right = mid - 1;
else
left = mid + 1;
}
}else{
left++;//right--;
}
}
return false;
}
}
上一篇题目:每天一道leetcode-33
本道题目是对上一篇题目的加强版，在有序数组的中加入了有重复数字这一条件，题目变得稍微难了一些些，思路也是很类似的，就是分情况讨论。
对于这种题目，数组，有序这两个字眼结合起来，就是要第一时间考虑到二分查找。
先举个例子，假设有旋转数组[3,3,3,4,5,6,1,2,3,3],以图形化的方式表示出这个数组，3,3,3,4,5,6为前半段，1,2,3,4为后半段，后续的图不是这个数组。
思路：由于无法确定target,nums[mid]谁大谁小，以及target和nums[mid]到底在前半段，还是在后一段，不同的情况下，对于令left = mid+1还是right = mid-1是不一样的情况，所以这里分情况进行讨论，把所有的情况讨论一遍，然后就知道，到底是变化left还是变化right，进而去缩小这个区间，找到我们要找到的数,在这里唯一不同的就是多了一种nums[mid]与nums[left]如果相等了的情况，该怎么处理。
nums[mid] >nums[left]
第10行，nums[mid]>nums[left]判断为真，说明nums[mid]在前半段。如下图所示
target>nums[mid]
紧接着到了12行，target>nums[mid],看图得知，target只能是在前半段。
所以观察得知，令left=mid+1往target去逼近。
target<nums[mid]
当12行代码判断为假，也就是要进入到14行。
而target小于nums[mid]时候，由于不知道target是在前半段还是后半段，所以的分情况讨论。
target<nums[mid]且target在前半段
当target在前半段，也就是代码第15行，target>nums[left],如下图所示。
观察图可知，16行，明显应该令right=mid-1,right减小去往target逼近。
target<nums[mid]且target在后半段
当target在后半段，也就是代码15行判断为假，也就是nums[left]>target，进入到18行。
观察图可知，明显应该是left=mid+1，来往target去逼近。
到这，10-20行代码解读完毕。
nums[mid]<nums[left]
当第10行代码判断为假，也就是nums[mid]<nums[left],nums[mid]落入到后半段，此时进入到代码21这个分支。如下图所示。
由于不知道target与nums[mid]的关系得分情况讨论。
target<nums[mid]
当target<nums[mid]时候，也就22行代码，观察上图得知，target只能在后半段，如下图所示。
明显应该是right=mid-1,来逼近taeget. ,23行代码所示。
target>nums[mid]
当22行代码判断为假，进入到25行代码，也就是target大于nums[mid]。
当target大于nums[mid]的时候，target可以在前半段大于nums[mid]，也可以在后半段大于nums[mid],所以得分两种情况讨论。
target>nums[mid]且target在前半段
target在前半段，也就是代码25行，target>nums[mid]
如上图所示，明显令right=mid-1去逼近target,也就是代码26行。
target>nums[mid]且target在后半段
target在后半段，也就是代码25行判断为假，target<nums[left]，进入到28行.
观察图得知，left=mid+1;
nums[mid]=nums[left]
当着二者相等的时候，无法讨论，这是为啥呢？
这里举个例子，帮助大家理解。
对于数组
[3,3,3,3,4,5,6,7]，nums[mid]=nums[left]对吧，这时候如果要找6,target=6,那么应该是left=mid+1;往6去逼近。
而对于数组
[3,3,3,3,4,5,6,7,1,2,3,3,3,3,3,3,3,3,3,3,3,3],nums[mid]=nums[left]也是相等的对吧，但是这是候去找6，就应该是right=mid-1,去逼近这个6。
所以对于这种nums[mid]=nums[left]的情况你无法去确定nums[mid]是在前半段还是后半段没所以也就无法讨论。
所以只能是一次移动一个去逼近target,也就是代码31行，left++;或者right--都可以去去逼近target。
结束语
总体来说思路与leetcode31这道理差不多，但是多了一个nums[mid]=nums[left]的情况，把这个情况单独拿出来谈论即可。
END