社区首页 >专栏 >每天一道leetcode-81

每天一道leetcode-81

乔戈里

发布于 2019-09-17 06:24:18

38800

文章被收录于专栏：Java那些事Java那些事

运行总次数：0

前言

目前准备每天刷一道题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]在前半段。如下图所示