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

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

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

01 PART

旋转排序数组最小值Ⅰ

这道题目有两个版本,一道简单,一道困难。我们从简单的开始讲起。

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

示例 1:

输入: [3,4,5,1,2] 输出: 1

示例 2:

输入: [4,5,6,7,0,1,2] 输出: 0

02 PART

题解分析

这道题目的关键点取决于是否可以想到二分,难点:无。但是如果把题中的条件,换成数组中元素可重复,本题的难度就会大幅上升。

当然,本题可以直接暴力搜索,但是这就就会被面试官撵出去。为了不被他撵出去,我们还是使用二分更为稳妥!在二分搜索中,我们找到区间的中间点并根据某些条件决定去区间左半部分还是右半部分搜索。但是麻烦的是,我们的数组被旋转了,因此肯定不能直接使用二分。那我们需要先观察一下,假若我们的原始数组如下:

无论怎么旋转,我们都可以得到一个结论,首元素 > 尾元素,像是下面这样。虽然不知道这个结论有什么用,但是我们先记下来。

继续进行观察,上面其实是两种极端情况,那如果普通的情况旋转,大概是下面这样:

问题似乎变得简单了,旋转将原数组一分为二,并且我们已知了首元素值总是大于尾元素,那我们只要找到将其一分为二的那个点(该点左侧的元素都大于首元素,该点右侧的元素都小于首元素),是不是就可以对应找到数组中的最小值。

然后我们通过二分来进行查找,先找到中间节点mid,如果中间元素大于首元素,我们就把mid向右移动。

如果中间元素小于首元素,我们就把mid向左移动。

根据分析,完成题解:

(java)

//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 {                                
                right = mid;
            }
        }
        return nums[left];
    }
};

(python)

//python
class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[right]:         
                left = mid + 1
            else:                               
                right = mid
        return nums[left]

(c)

//c
int findMin(int* nums, int numsSize){
    int left=0;
    int right=numsSize-1;
    while(right>left)
    {
        int mid=left+(right-left)/2;
        if(nums[mid]>nums[right])
            left=mid+1;
        else
            right=mid;
    }
    return nums[left];
}

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

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

03

PART

课后思考

本题有多种变形,是一道练习二分法的绝佳题目。比如“把元素中不可重复的条件去掉”,又或者是“编写一个函数来判断目标值是否在数组中”等等,不同的改动,都会对题目解题方式有略微的影响,但是万变不离其宗,统统都是二分法。

其他的就不啰嗦了,明天将为大家答疑分析,解决“元素可重复”的版本。所以,今天的问题你学会了吗,评论区留下你的想法!

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    程序员小浩
  • 漫画:BAT必考题目 (最小的k个数)

    最小的k个数:输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

    程序员小浩
  • 漫画:如何使用二分法回滚代码?

    一般我们使用 git reset --hard #version 来进行回滚到指定版本的代码。

    程序员小浩
  • LeetCode题目35:搜索插入位置

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

    二环宇少
  • [LeetCode] 153. Find Minimum in Rotated Sorted Array

    【原题】 Suppose an array sorted in ascending order is rotated at some pivot unkno...

    用户1148830
  • 终于知道两个模板的区别了!【手绘漫画】图解LeetCode之在排序数组中查找元素的第一个和最后一个位置(LeetCode 34)

    最后返回的值写 left 或者 right 都是没问题的!因为 while 的结束条件是 left 和 right 相等。

    我是管小亮
  • Leetcode 33. Search in Rotated Sorted Array

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 用C++写二分查找了!【手绘漫画】图解LeetCode之搜索插入位置(LeetCode 35)

    正常的二分查找,除了两个特殊的条件,即,如果数组中没有 target,小于最小值或者大于最大值,则返回插入的位置。

    我是管小亮
  • 【手绘漫画】图解LeetCode之寻找峰值(LeetCode 162题)

    首先分析一下情况,如果 mid 一直比右侧的数小,那么 mid 处的值肯定不是峰值。

    我是管小亮
  • 搜索插入位置

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

    你的益达

扫码关注云+社区

领取腾讯云代金券