每天一道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