[Leetcode] Find Minimum in Rotated Sorted Array 找旋

notebin 發布于2019-08-14 12:24 / 3151人閱讀

摘要：二分迭代法復雜度時間空間遞歸棧空間思路找旋轉數組的起點，實際上類似找一個山谷，只要兩邊都比中間高就對了，這和這題很像。

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()

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

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