旋轉數組的最小數字

LinkedME2016 發布于2019-08-16 12:35 / 2372人閱讀

摘要：把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組為的一個旋轉，該數組的最小值為。但我們不能區分出最小的數字在的左邊還是右邊，就沒法進行判斷了。

把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大于0，若數組大小為0，請返回0.

發現用二分法解決這個問題很好，{3,4,5,1,2}可以分成兩個排好序的子數組{3,4,5}{1,2}，而左邊的每個數一定大于右邊的每個數，所以可以聲明兩個索引left=0，right=length-1，mid=left（為啥這么設置初始值請看代碼注釋）.
開始循環，循環條件為list[left] >= list[right]。我們要做的事情就是讓left一直處于第一個數組里且不斷接近第一個數組尾，讓right一直處于數組二且不斷接近數組二的頭。讓mid等于（left+right）/2，當mid大于left時，說明此時mid還在第一個數組里，這時就讓left=mid；繼續循環mid再等于（left+right）/2，假設此時mid小于left了，那么它一定處于第二個數組里了，而且它也小于right（因為right時第二個數組當前最大的）.當left+1==right的時候就可以跳出循環了，因為此時right就是我們要找的元素。

 public class Jianzhi{

    public static void main (String[] args){
        int[] num = {3,4,5,1,2};
        int m = find(num ) ;
        System.out.println(m);
    }
    public static int find(int[] list) {
        if(list == null){  //數組為null時
            return -1 ;
        }
        if(list.length == 0 ){  //數組長度為0則返回0
            return 0 ;
        }
        int left = 0 ;    
        int right = list.length - 1 ;
        int mid = left ;    //注意：這一步讓mid等于left是有用意的，如果list是排好序的，
                            //那么直接返回list[mid] 
        while(list[left] >= list[right]){ 
            if(left + 1 == right){
                    return right ;
            }
            mid = (left + right) / 2 ;
            if(list[mid] == list[left] && list[mid] == list[right]){
                return minInOrder(list,left,right);
            }
            if(list[mid] >= list[left]){
                left = mid ;
            }
            if(list[mid] <= list[right] ){
                right = mid  ;
            }
        }
        return list[mid] ;
    }
public static int minInOrder(int[] list , int left , int right ){
    int result = list[left] ;
    for(int i = left+1 ; i < right ; i++){
        if(result > list[i] ){
            result = list[i] ;
        }
    }
    return result ;
}

}

可能大家比較疑惑為什么有以下這句：

if(list[mid] == list[left] && list[mid] == list[right]){
                return minInOrder(list,left,right);
            }

考慮下面這種情況

此時第一個和第二個索引以及mid索引指向的指都是1，三個數字相同。但我們不能區分出最小的數字在mid的左邊還是右邊，就沒法進行判斷了。此時，就不得不采用順序查找方法：

public static int minInOrder(int[] list , int left , int right ){
        int result = list[left] ;
        for(int i = left+1 ; i < right ; i++){
            if(result > list[i] ){
                result = list[i] ;
            }
        }
        return result ;
    }

整個算法最重要的還是讓left和right都往兩個數組的公共邊界靠攏。

完畢。

GPU云服務器云服務器旋轉數組數組中未出現的數字二維數組旋轉數組最小值

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

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

【劍指offer】7.旋轉數組的最小數字

摘要：題目把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個非減排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組為的一個旋轉，該數組的最小值為。出現這種情況的類似，此時最小數字一定在的右邊。題目把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個非減排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3,4,5,1,2}為{1,...

W4n9Hu1 2019-08-23 14:48 評論0 收藏0
數據結構與算法（查找和排序） --javascript語言描述

摘要：如此，便可以縮小搜索范圍，提高時間復雜度，最終第一個指針指向前面子數組的最后一個元素，而第二個指針指向后面子數組的第一個元素，它們處于相鄰位置，而第二個指針指向的剛好是最小的元素。旋轉數組的最小數字（二分查找）把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3,4,5,1,2}為{1,2,3...

Stardustsky 2019-08-26 11:45 評論0 收藏0
算法練習6：旋轉數組的最小數字

摘要：題目有一個長度為的非降序數組，比如，將它進行旋轉，即把一個數組最開始的若干個元素搬到數組的末尾，變成一個旋轉數組，比如變成了，或者這樣的。請問，給定這樣一個旋轉數組，求數組中的最小值。題目:有一個長度為 n 的非降序數組，比如[1,2,3,4,5]，將它進行旋轉，即把一個數組最開始的若干個元素搬到數組的末尾，...

DirtyMind 2021-11-25 09:43 評論0 收藏0
劍指Offer(Java版) 持續更新中

摘要：面試題從尾到頭打印鏈表輸入一個鏈表，從尾到頭打印鏈表每個節點的值面試題重建二叉樹輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。隊列中的元素為類型。其中負數用補碼表示。面試題2 單例(之前有整理，略) 面試題3 二維數組中的查找 public boolean find(int target, int [][] arra...

justCoding 2019-08-15 11:04 評論0 收藏0
70道前端LeetCode題目集合及視頻講解（持續更新中...）

前端LeetCode刷題下面是已刷的題目的目錄。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，歡迎關注。數組類 26 刪除排序數組中的重復項 27 移除元素 35 搜索插入位置 66 加1 80 medium 刪除排序數組中的重復項2 88 合并兩個有序數組 167 兩數之和II - 輸入有序數組 118 楊輝三角 169 easy 求眾數 1...

mayaohua 2019-08-26 10:46 評論0 收藏0