[LintCode/LeetCode] Find Minimum in Rotated Sorted

cgh1999520 发布于2019-08-14 15:22 / 2083人阅读

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

Find Minimum in Rotated Sorted Array Problem

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.

Notice

You may assume no duplicate exists in the array.

Example

Given [4, 5, 6, 7, 0, 1, 2] return 0

Note

排序数组中找最小值或最大值的题目，很明显可以使用二分法。我们先来看看rotated sorted array有哪些情况，再确定如何使用二分法：

        //LO   M   HI
        // 789123456
        // 678912345
        // 456789123
        // 123456789

上面的例子分别是较小元素，最小元素，较大元素，中位数在中点的情况。可见，用队首元素num[start]和中点num[mid]比较没有意义。因此，只判断终点和中点元素的大小关系即可。

Solution

public class Solution {
    public int findMin(int[] num) {
        int start = 0, end = num.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (num[end] > num[mid]) end = mid;
            else start = mid;
        }
        return num[start] < num[end] ? num[start] : num[end];
    }
}

Find Minimum in Rotated Sorted Array Problem

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.

Example

Given [4,4,5,6,7,0,1,2] return 0

Note

上面这些case是很难直接用二分法判断的，只能对中点两边同时使用二分法递归，或者完全遍历数组求最优解。
二分法递归的步骤是：建立helper()函数，当中点值大于等于末位值，夹逼到后半段，舍弃中间值；当中点值小于等于末位值，夹逼到前半段，不舍弃中间值。这里有一种情况是（上述后三个case），中点值和末位相等。此时，两边同时递归，并返回两边递归值的较小值。当首位和末位重合，说明已夹逼得到最小值。

Solution

二分法递归

public class Solution {
    public int findMin(int[] num) {
        return helper(num, 0, num.length-1);
    }
    public int helper(int[] num, int start, int end) {
        if (start == end) return num[start];
        int mid = start + (end - start) / 2;
        int left = Integer.MAX_VALUE, right = left;
        if (num[mid] >= num[end]) {
            right = helper(num, mid+1, end);
        }
        if (num[mid] <= num[end]) {
            left = helper(num, start, mid);
        }
        return Math.min(left, right);
    }
}

暴力循环

public class Solution {
    public int findMin(int[] num) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < num.length; i++) {
            min = Math.min(num[i], min);
        }
        return min;
    }
}

云服务器 GPU云服务器 FIND_IN_SET Rotated Minimum Sorted

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

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

[LintCode/LeetCode] Search in Rotated Sorted Arra

摘要：找中点若起点小于中点，说明左半段没有旋转，否则说明右半段没有旋转。在左右半段分别进行二分法的操作。只判断有无，就容易了。还是用二分法优化 Search in Rotated Sorted Array Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 ...

U2FsdGVkX1x 2019-08-14 15:41 评论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
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
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
[LintCode/LeetCode] Minimum Window Substring

Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...

Corwien 2019-08-14 15:43 评论0 收藏0