leetcode153-154 find minimum rotated sorted array

DrizzleX 發(fā)布于2019-08-16 10:42 / 2319人閱讀

摘要：題目要求假設有一個升序排序的數(shù)組，在某個節(jié)點處斷開并調換了順序。尋找這個斷開數(shù)組中的最小元素。但是如果我們將頭尾的重復元素清楚，而只是在數(shù)組中間存在重復元素的話，如，這樣并不會影響升序數(shù)組位置的判斷。

題目要求

Suppose an array sorted in ascending order 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.

假設有一個升序排序的數(shù)組，在某個節(jié)點處斷開并調換了順序。尋找這個斷開數(shù)組中的最小元素。

當數(shù)組中不存在重復的元素

通過二分法來實現(xiàn)在logN的時間中找到最小的值。通過二分法往往會有以下幾種情況

位于一個升序的數(shù)組中，也就是左側值小于右側值，這時候左側值就是最小值。

左側值小于中間值，那么中間值左側一定是升序數(shù)組，所以最小值在右側

中間值小于右側值，那么中間值右側一定是升序數(shù)組，所以最小值要么在左側，要么就是中間值

代碼如下：

    public int findMin(int[] nums) {
        int leftPointer = 0;
        int rightPointer = nums.length-1;
        while(leftPointer
數(shù)組中存在重復的元素
唯一會影響遍歷的是數(shù)組的開頭和結尾處的元素為重復元素，如[4,4,1,4,4]，在這種情況下就無法通過上面一種方法來識別出升序數(shù)組位于中間值的左側或是右側。但是如果我們將頭尾的重復元素清楚，而只是在數(shù)組中間存在重復元素的話，如[4,1,1,1,3]，這樣并不會影響升序數(shù)組位置的判斷。
  public int findMin2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        
        int start = 0, end = nums.length - 1;
        
        while (nums[end] == nums[start] && end > start) {
            end--;
        }
        
        while (start < end) {
            if (nums[start] < nums[end]) {
                return nums[start];
            }
            
            int mid = start + (end - start) / 2;
            if (nums[mid] >= nums[start]) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        
        return nums[start];
    }  

想要了解更多開發(fā)技術，面試教程以及互聯(lián)網公司內推，歡迎關注我的微信公眾號！將會不定期的發(fā)放福利哦~

GPU云服務器云服務器 sorted-array array_find Minimum Leetcod

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/70285.html

[LintCode/LeetCode] Find Minimum in Rotated Sorted

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

cgh1999520 2019-08-14 15:22 評論0 收藏0
[Leetcode] Find Minimum in Rotated Sorted Array 找旋

摘要：二分迭代法復雜度時間空間遞歸?？臻g思路找旋轉數(shù)組的起點，實際上類似找一個山谷，只要兩邊都比中間高就對了，這和這題很像。 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
LeetCode 154 在有序旋轉數(shù)組中找最小-2

摘要：難度就是說一個從小到大排序好的數(shù)組循環(huán)移位不知多少次，求最小值。比如全部是的數(shù)列，和除了某位置有個，其余全部是的數(shù)列，都是合法的。在這里，測試用例也進行了增加，盡量覆蓋各種奇葩情況。 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

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0