[Leetcode] Find Minimum in Rotated Sorted Array 找旋

notebin 发布于2019-08-14 12:24 / 3156人阅读

摘要：二分迭代法复杂度时间空间递归栈空间思路找旋转数组的起点，实际上类似找一个山谷，只要两边都比中间高就对了，这和这题很像。

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 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

二分迭代法 复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

4 5 6 7 0 1 2
      |
    | |
  | | |
| | | |
| | | |
| | | |     |
| | | |   | |

找旋转数组的起点，实际上类似找一个山谷，只要两边都比中间高就对了，这和Find Peak Element这题很像。我们不断地取中点，找左右两侧较小的那一侧，直到找到一个点比左右两边都低。

注意

在二分到两头的时候要特殊处理一下，返回两头和两头第二个中最小的。

代码

public class Solution {
    public int findMin(int[] nums) {
        for(int min = 0, max = nums.length - 1, mid = max / 2; min <= max; mid = (min + max)/2){
            // 如果找到最左边，返回较小的那个
            if(mid == 0) return Math.min(nums[mid],nums[max]);
            // 如果找到最右边，返回较小的那个
            if(mid == nums.length - 1) return Math.min(nums[mid],nums[min]);
            // 如果两边都比中间高，返回中间那个
            if(nums[mid] < nums[mid-1] && nums[mid] < nums[mid+1]) return nums[mid];
            // 否则，继续搜索较小的那一半，找到低谷
            if(nums[mid] > nums[max]){
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        return nums[0];
    }
}

二分模板

public class Solution {
    public int findMin(int[] nums) {
        int min = 0, max = nums.length - 1;
        while(min <= max){
            int mid = min + (max - min) / 2;
            if(mid == 0) return Math.min(nums[mid], nums[max]);
            if(mid == nums.length - 1) return Math.min(nums[mid], nums[min]);
            if(nums[mid + 1] >= nums[mid] && nums[mid - 1] >= nums[mid]){
                return nums[mid];
            } else if(nums[mid] > nums[max]){
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        return nums[0];
    }
}

二分递归法 复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

递归法实现起来更加简洁清晰。当min等于max时，我们锁定了那个最小值。那如何判断在哪一半呢，如果num[max] > num[mid]，说明右边都是有序的，所以那个旋转点必在左半边，也就是min到mid之间，如果num[max] < num[mid]，说明右边有问题，不过mid点本身肯定不是最小值，他已经大于num[max]了，所以在mid+1和max之间

注意

min == max时随便返回一个

代码

public class Solution {
    public int findMin(int[] num) {
        return findMin(num, 0, num.length-1);
    }
    private int findMin(int[] num, int min, int max){
        if(min == max){
            return num[min];
        }
        int mid = (min+max)/2;
        if(num[max] > num[mid]){
            return findMin(num, min, mid);
        } else {
            return findMin(num, mid+1, max);
        }
    }
}

Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why? 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.

The array may contain duplicates.

二分递归法 复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

如果有重复的话，一旦中间和右边是相等的，就无法确定是否在左半边还是右半边，这时候我们必须对两边都递归求解。如果nums[max]大于等于nums[mid]，则右边有可能有，如果nums[max]小于等于nums[mid]，则左边有可能有。

注意

要先将左和右的最小值初始化最大整数，然后求解后，最后返回其中较小的那个

代码

public class Solution {
    public int findMin(int[] nums) {
        return findMin(nums, 0, nums.length - 1);
    }
    
    public int findMin(int[] nums, int min , int max){
        if(min == max){
            return nums[min];
        }
        int mid = (min + max) / 2;
        // 先将右边和左边可能找到的值都初始化为最大
        int right = Integer.MAX_VALUE, left = Integer.MAX_VALUE;
        // 找出右边可能的旋转点
        if(nums[mid] >= nums[max]){
            right = findMin(nums, mid + 1, max);
        }
        // 找出左边可能的旋转点
        if (nums[mid] <= nums[max]) {
            left = findMin(nums,min, mid);
        }
        // 返回两个中更小的
        return Math.min(right,left);
    }
}

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

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

转载请注明本文地址：https://www.ucloud.cn/yun/64455.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
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
Find Minimum in Rotated Sorted Array

摘要：题目思路个人觉得这是一道值得回味的二分法题目。与给出的二分法搜索比，这道题目的是未知的，并且是。我个人是从观察给出的例子入手的。我本人走的弯路是，过于专注于，从而逻辑变得复杂。其实，，和步就可以帮助我们顺利找到最小值。题目 http://www.lintcode.com/en/pr... Suppose a sorted array is rotated at some pivot ...

DataPipeline 2019-07-30 14:38 评论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