专栏首页小浩算法漫画:知乎面试题(旋转数组最小值Ⅱ - 进阶版)

漫画:知乎面试题(旋转数组最小值Ⅱ - 进阶版)

今天是小浩算法“365刷题计划”第72天。继续为大家讲解二分法系列篇 - 旋转排序数组最小值Ⅱ(进阶版)。话不多说,直接看题:

01 PART

旋转排序数组最小值Ⅱ

昨天为大家讲解了元素不可重复的版本,那如果元素重复该如何处理呢?

第154题:假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1:

输入: [1,3,5]

输出: 1

示例 2:

输入: [2,2,2,0,1]

输出: 0

说明:

这道题是 寻找旋转排序数组中的最小值 的延伸题目。

允许重复会影响算法的时间复杂度吗?会如何影响,为什么?

02 PART

题目回顾

之前我也说过,通过改变题中条件,使得题目难度上升的做法。在算法题目的设计中,是一种非常常见的手段。本题就是这样,从中等变成了困难。

(通过改变题目,使得难度上升)

在讲解本题之前,首先要对昨天的题目进行一个答疑。昨天有人问我为什么题目中讲的是与left进行比较,但是最后代码中写的时候变成了和right比较。这个确实是我讲的时候讲忘了,但是这其实是一个思维转化的问题:因为在旋转之前的原数组是一个递增序列,那一定是左边的数小,右边的数大,而我们要找的是最小值,所以比较偏向左找。那如果和left进行比较,其实也是完全ok的,那我们的思路就变成了找到偏右的最大值,进而向右再移动一位,自然也就是最小值。如果不能理解的话,可以回顾一下昨天的文章:

漫画:知乎面试题(旋转数组最小值Ⅰ - 基础版)

并且我这里对昨天的题目,补上一个和left对比的版本,供大家参考学习(昨天没有给Go的示例,所以今天补一个Go的)

//go
func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)>>1 + 1
        if nums[left] < nums[mid] {
            left = mid
        } else if nums[left] > nums[mid] {
            right = mid - 1
        }
    }
    return nums[(right+1)%len(nums)]
}

上面的代码有两处需要说明,第一:mid中最后加1的目的,是为了使得mid更加靠近right,增加容错性。当然,你写到里边也是可以的,甚至更好。我怕大家看不懂,所以写在外面了。第二:最后一行代码取模,是需要考虑最大值刚好在最右边的情况。

03 PART

题解分析

二分查找的本质,其实就是通过收敛查找空间,找到目标值的一种方式。请大家认真阅读这句话。不管是采用不同的mid定义方式,又或者是不一样的while条件,统统都是为了这个目的。在完成这个目的的基础上,我们才去考虑如何减少冗余代码,减少循环次数等等,完成进一步的优化。

现在再来看今天的题目。相对比昨天题目而言,其实只是多了nums[mid] 等于 nums[right] 时的额外处理。(当然, 如果是和left进行比较,就是nums[mid]等于nums[left])

对比一下下面两个图:

(无重复)
(有重复)

其实直接就可以给出代码了:

//java
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1; 
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                right--;
            }
        }
        return nums[left];
    }
};

郑重申明(读我的文章必看):

  • 本系列所有教程都不会用到复杂的语言特性,大家无须担心没有学过相关语法,算法思想才是最重要的!
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode进行过测试运行。

如果我们再对比一下代码的差异,就会非常的明显:

(左边是有重复,右边是无重复)

可以看到在 nums[mid] 等于 nums[right] 时的情况下,我们只多了一个 right-1 的操作。这里需要额外说明的是,为什么要这样做?我看leetcode上的题解,这块很多都是长篇大论,其实没那么复杂,一句话就可以给你讲明白,看看下面这个!

因为 mid 和 right 相等时,最小值既可能在左边,又可能在右边,所以此时自然二分思想作废,咱们就砍掉一个右边界。说白了,就是让子弹再飞一会儿

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

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

原始发表时间:2020-03-29

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:知乎面试题(旋转数组最小值Ⅰ - 基础版)

    今天是小浩算法“365刷题计划”第71天。继续为大家讲解二分查找,分享一道知乎面试题。话不多说,直接看题。

    程序员小浩
  • 漫画:常考的荷兰国旗问题你还不会吗?(初级)

    "荷兰国旗问题" 是计算机科学中的一个经典题目,它是由Edsger Dijkstra提出的。荷兰国旗由红、白、蓝三色组成。

    程序员小浩
  • 漫画:经典鹅厂面试题(2Sum,3Sum,4Sum)

    该题为 二数之和 的进阶版本,当然还有一个进阶版本为 四数之和。我们将会一一进行分析!

    程序员小浩
  • [算法总结] 二分查找

    二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。

    尾尾部落
  • LeetCode-15-3Sum

    Given an array S of n integers, are there elements a, b, c in S such that a + b ...

    欠扁的小篮子
  • 打卡群刷题总结0727——搜索旋转排序数组 II

    链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii

    木又AI帮
  • [Leetcode][python]Sort Colors/颜色分类

    给出一个由红、白、蓝三种颜色组成的数组,把相同颜色的元素放到一起,并整体按照红、白、蓝的顺序。用0表示红色,1表示白色,2表示蓝色。这题也称为荷兰国旗问题。

    后端技术漫谈
  • 【Leetcode】81. 搜索旋转排序数组 II

    ( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

    Leetcode名企之路
  • [Leetcode][python]搜索旋转排序数组/搜索旋转排序数组 II

    把一个严格升序的数组进行旋转,如[0,1,2,3,4,5]旋转3位成为[3,4,5,0,1,2]。在这样的数组中找到目标数字。如果存在返回下标,不存在返回-1。...

    后端技术漫谈
  • 【剑指offer:0~n-1中缺失的数字】二分查找的妙用

    题目描述:一个长度为 n-1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 ~ n-1 之内。在范围 0 ~ n-1 内的 n 个数字中有且只...

    心谭博客

扫码关注云+社区

领取腾讯云代金券