[LintCode/LeetCode] Find Minimum in Rotated Sorted

cgh1999520 發布于2019-08-14 15:22 / 2086人閱讀

摘要：排序數組中找最小值或最大值的題目，很明顯可以使用二分法。因此，只判斷終點和中點元素的大小關系即可。這里有一種情況是上述后三個，中點值和末位相等。此時，兩邊同時遞歸，并返回兩邊遞歸值的較小值。當首位和末位重合，說明已夾逼得到最小值。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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