首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >漫画:知乎面试题(旋转数组最小值Ⅱ - 进阶版)

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

作者头像
程序员小浩
修改2020-03-30 16:33:34
5810
修改2020-03-30 16:33:34
举报
文章被收录于专栏:小浩算法小浩算法

今天是小浩算法“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 相等时,最小值既可能在左边,又可能在右边,所以此时自然二分思想作废,咱们就砍掉一个右边界。说白了,就是让子弹再飞一会儿

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-03-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 小浩算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档