专栏首页Java那些事每天一道leetcode-81

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

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli),作者:乔戈里qgl

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每天一道leetcode-153

    目前准备每天刷一道题leetcode的题目,以此来激励那些零基础入门的人,千万不要被什么科班和非科班的说法吓倒了,计算机这个行业只要你肯努力,没有什么逾越不了的...

    乔戈里
  • 每天一道leetcode154-寻找旋转排序数组(有重复数字)中的最小值

    今天的题目是寻找旋转排序数组(有重复数字)中的最小值 II,这道题目是在之前做过的这道题目的升级版,这是上一道题目。

    乔戈里
  • 每天一道leetcode-33

    目前准备每天刷一道题leetcode的题目,以此来激励那些零基础入门的人,千万不要被什么科班和非科班的说法吓倒了,计算机这个行业只要你肯努力,没有什么逾越不了的...

    乔戈里
  • BAT面试算法进阶(1)-两个数求和

    Given an array of integers, return indices of the two numbers such that they add...

    CC老师
  • 每天一道leetcode-153

    目前准备每天刷一道题leetcode的题目,以此来激励那些零基础入门的人,千万不要被什么科班和非科班的说法吓倒了,计算机这个行业只要你肯努力,没有什么逾越不了的...

    乔戈里
  • Leetcode 287. Find the Duplicate Number

    Given an array nums containing n + 1 integers where each integer is between 1 a...

    triplebee
  • Leetcode 287. Find the Duplicate Number

    Given an array nums containing n + 1 integers where each integer is between 1 a...

    triplebee
  • leetcode 34 Search for a Range

    @坤的
  • 【leetcode刷题】 20T19-在排序数组中查找元素的第一个和最后一个位置

    https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sort...

    木又AI帮
  • 【leetcode刷题】T12-搜索旋转排序数组II

    今天分享leetcode第12篇文章,也是leetcode第81题—搜索旋转排序数组II(Search in Rotated Sorted Array II),...

    木又AI帮

扫码关注云+社区

领取腾讯云代金券