Find Minimum in Rotated Sorted Array

DataPipeline 发布于2019-07-30 14:38 / 1761人阅读

摘要：题目思路个人觉得这是一道值得回味的二分法题目。与给出的二分法搜索比，这道题目的是未知的，并且是。我个人是从观察给出的例子入手的。我本人走的弯路是，过于专注于，从而逻辑变得复杂。其实，，和步就可以帮助我们顺利找到最小值。

题目

http://www.lintcode.com/en/pr...

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

思路

个人觉得这是一道值得回味的二分法题目。与给出target的二分法搜索比，这道题目的target是未知的，并且array是rotated。我个人是从观察给出的例子入手的。
通过观察这个例子，我们发现以下特征：

最小值是唯一一个比它左右相邻数字都小的数字

当中位数比start 和 end 都大的时候，最小值在右边

当中位数比start 和 end 都小的时候，最小值在左边

当中位数比start大，比end小的时候，我们进入了sorted的array，最小值也是在左边

那么我们做这道题目的目的，就是通过2，3这两步，进入最小值所在的sorted的array，从而进行第4步。我本人走的弯路是，过于专注于1，从而逻辑变得复杂。其实2，3，和4步就可以帮助我们顺利找到最小值。

代码

class Solution:
    # @param nums: a rotated sorted array
    # @return: the minimum number in the array
    def findMin(self, nums):
        # write your code here
        if nums is None or len(nums) == 0:
            return -1
        start = 0
        end = len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] > nums[end]:
                start = mid
            elif nums[mid] < nums[start] or (nums[mid] < nums[end] and nums[mid] > nums[start]):
                end = mid
        return nums[start] if nums[start] < nums[end] else nums[end]

体会

这道题目的个人体会就是如果用二分法处理sorted array，核心逻辑在于把已知input分为左右两部分，再从中入手。

云服务器 GPU云服务器 sorted-array array_find FIND_IN_SET in_array()

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/40819.html

[LintCode/LeetCode] Find Minimum in Rotated Sorted

摘要：排序数组中找最小值或最大值的题目，很明显可以使用二分法。因此，只判断终点和中点元素的大小关系即可。这里有一种情况是上述后三个，中点值和末位相等。此时，两边同时递归，并返回两边递归值的较小值。当首位和末位重合，说明已夹逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

cgh1999520 2019-08-14 15:22 评论0 收藏0
[Leetcode] Find Minimum in Rotated Sorted Array 找旋

摘要：二分迭代法复杂度时间空间递归栈空间思路找旋转数组的起点，实际上类似找一个山谷，只要两边都比中间高就对了，这和这题很像。 Find Minimum in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 ...

notebin 2019-08-14 12:24 评论0 收藏0
leetcode153-154 find minimum rotated sorted array

摘要：题目要求假设有一个升序排序的数组，在某个节点处断开并调换了顺序。寻找这个断开数组中的最小元素。但是如果我们将头尾的重复元素清楚，而只是在数组中间存在重复元素的话，如，这样并不会影响升序数组位置的判断。题目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor...

DrizzleX 2019-08-16 10:42 评论0 收藏0
LeetCode 154 在有序旋转数组中找最小-2

摘要：难度就是说一个从小到大排序好的数组循环移位不知多少次，求最小值。比如全部是的数列，和除了某位置有个，其余全部是的数列，都是合法的。在这里，测试用例也进行了增加，尽量覆盖各种奇葩情况。 Follow up for Find Minimum in Rotated Sorted Array:What if duplicates are allowed?Would this affect th...

evin2016 2019-08-14 17:02 评论0 收藏0
LeetCode 153 在有序旋转数组中找最小-1

摘要：难度就是说一个从小到大排序好的数组循环移位不知多少次，求最小值。数组无重复值无重复的话就比较简单，用二分查找即可。当前游标始终是左右游标中点位置，与左右游标的数值比较。解法有几个要点基本终止条件为左边的数比当前的数大，那么当前数即是最小值。 Question:Suppose a sorted array is rotated at some pivot unknown to you b...

MkkHou 2019-08-14 16:59 评论0 收藏0