每日算法系列【LeetCode 153】寻找旋转排序数组中的最小值

godweiyang

发布于 2020-03-24 10:46:01

5170

发布于 2020-03-24 10:46:01

文章被收录于专栏：算法码上来

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

(例如，数组 [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

题解

这题如果直接遍历一遍的话，时间复杂度是，也能过。但是这题显然想要你更快，也就是用的时间复杂度来做出来，那我们只能选择用二分法。

因为序列从中间切开来，然后调换过顺序，所以是先上升，再下降一下，然后再上升。并且第二段上升的最大值是一定小于第一段上升的最小值的，所以最小值一定是第二段的第一个数。

假设我们二分的时候，左端点 l ，右端点 r ，中间点是 m 。

如果，那说明左端点在第一段，右端点在第二段。这时如果，那么 m 也在第一段，所以 l 需要右移；否则的话 m 在第二段， r 需要左移。

如果，那么两个端点都在第二段，是单调上升的，那最小值一定就是 l 。

代码

c++

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (nums[l] > nums[r]) {
                if (nums[m] >= nums[l]) {
                    l = m + 1;
                } else {
                    r = m;
                }
            } else {
                r = l;
            }
        }
        return nums[r];
    }
};

python

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums)-1
        while l < r:
            m = (l + r) // 2
            if nums[l] > nums[r]:
                if nums[m] >= nums[l]:
                    l = m + 1
                elif nums[m] < nums[r]:
                    r = m
            else:
                r = l
        return nums[r]

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-01-27，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自算法码上来微信公众号，前往查看

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

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度