153. 寻找旋转排序数组中的最小值


153. 寻找旋转排序数组中的最小值


class Solution {
    public int findMin(int[] nums) {

        // If the list has just one element then return that element.
        if (nums.length == 1) {
            return nums[0];
        }

        // initializing left and right pointers.
        int left = 0, right = nums.length - 1;

        // if the last element is greater than the first element then there is no rotation.
        // e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
        // Hence the smallest element is first element. A[0]
        if (nums[right] > nums[0]) &#123;
            return nums[0];
        &#125;

        // Binary search way
        while (right >= left) &#123;
            // Find the mid element
            int mid = left + (right - left) / 2;

            // if the mid element is greater than its next element then mid+1 element is the smallest
            // This point would be the point of change. From higher to lower value.
            if (nums[mid] > nums[mid + 1]) &#123;
                return nums[mid + 1];
            &#125;

            // if the mid element is lesser than its previous element then mid element is the smallest
            if (nums[mid - 1] > nums[mid]) &#123;
                return nums[mid];
            &#125;

            // if the mid elements value is greater than the 0th element this means
            // the least value is still somewhere to the right as we are still dealing with elements
            // greater than nums[0]
            if (nums[mid] > nums[0]) &#123;
                left = mid + 1;
            &#125; else &#123;
                // if nums[0] is greater than the mid value then this means the smallest value is somewhere to
                // the left
                right = mid - 1;
            &#125;
        &#125;
        return -1;
    &#125;

// 作者:LeetCode
// 链接:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/solution/xun-zhao-xuan-zhuan-pai-lie-shu-zu-zhong-de-zui-xi/
&#125;

复杂度分析

  • 时间复杂度:和二分搜索一样 O(log⁡N)
  • 空间复杂度:O(1)

分析

如果数组没有被旋转,是升序排列,就满足 last element > first element。
image.png
上面的例子中 3 < 4,因此数组旋转过了。这是因为原先的数组为 [2, 3, 4, 5, 6, 7],通过旋转较小的

[2, 3] 移到了后面,也就是 [4, 5, 6, 7, 2, 3]。因此旋转数组中第一个元素 [4] 变得比最后一个元素大。

这意味着在数组中你会发现一个变化的点,这个点会帮助我们解决这个问题,我们称其为变化点。

在这个改进版本的二分搜索算法中,我们需要找到这个点。下面是关于变化点的特点

所有变化点左侧元素 > 数组第一个元素

所有变化点右侧元素 < 数组第一个元素

算法

找到数组的中间元素 mid。
如果中间元素 > 数组第一个元素,我们需要在 mid 右边搜索变化点。
如果中间元素 < 数组第一个元素,我们需要在 mid 左边搜索变化点。
image.png
上面的例子中,中间元素 6 比第一个元素 4 大,因此在中间点右侧继续搜索。

当我们找到变化点时停止搜索,当以下条件满足任意一个即可:
nums[mid] > nums[mid + 1],因此 mid+1 是最小值。
nums[mid - 1] > nums[mid],因此 mid 是最小值。

作者:LeetCode
链接:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/solution/xun-zhao-xuan-zhuan-pai-lie-shu-zu-zhong-de-zui-xi/



文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
55. 跳跃游戏 55. 跳跃游戏
55. 跳跃游戏难度中等给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。 示例  1:输入:nums = [2,3,1,1,4]输出:tru
下一篇 
516. 最长回文子序列 516. 最长回文子序列
516. 最长回文子序列难度中等给定一个字符串 s ,找到其中最长的回文子序列,并返回该序列的长度。可以假设 s 的最大长度为 1000 。 示例 1:输入:“bbbab”输出:4一个可能的最长回文子序列为 “bbbb”。示例 2:输入:
2021-02-28 future
  目录