国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

【劍指offer】7.旋轉(zhuǎn)數(shù)組的最小數(shù)字

W4n9Hu1 / 1216人閱讀

摘要:題目把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾,我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個非減排序的數(shù)組的一個旋轉(zhuǎn),輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組為的一個旋轉(zhuǎn),該數(shù)組的最小值為。出現(xiàn)這種情況的類似,此時最小數(shù)字一定在的右邊。

題目

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

基本思路

肯定不能直接遍歷,失去了這道題的意義

旋轉(zhuǎn)數(shù)組其實是由兩個有序數(shù)組拼接而成的,因此我們可以使用二分法,只需要找到拼接點即可。

(1)array[mid] > array[high]:

出現(xiàn)這種情況的array類似[3,4,5,6,0,1,2],此時最小數(shù)字一定在mid的右邊。
low = mid + 1

(2)array[mid] == array[high]:

出現(xiàn)這種情況的array類似 [1,0,1,1,1] 或者[1,1,1,0,1],此時最小數(shù)字不好判斷在mid左邊
還是右邊,這時只好一個一個試 。
high = high - 1

(3)array[mid] < array[high]:

出現(xiàn)這種情況的array類似[2,2,3,4,5,6,6],此時最小數(shù)字一定就是array[mid]或者在mid的左
邊。因為右邊必然都是遞增的。
high = mid

代碼
function minNumberInRotateArray(arr)
{
    let len = arr.length;
    if(len == 0)  return 0;
    let low = 0, high = len - 1;
    while(low < high) {
        let mid = low + Math.floor((high-low)/2);
        if(arr[mid] > arr[high]) {
            low = mid + 1;
        } else if(arr[mid] == arr[high]) {
            high = high - 1;
        } else {
            high = mid;
        }
    }
 
    return arr[low];
}
擴(kuò)展

二分查找

        function binarySearch(data, arr, start, end) {
            if (start > end) {
                return -1;
            }
            var mid = Math.floor((end + start) / 2);
            if (data == arr[mid]) {
                return mid;
            } else if (data < arr[mid]) {
                return binarySearch(data, arr, start, mid - 1);
            } else {
                return binarySearch(data, arr, mid + 1, end);
            }
        }

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

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/101168.html

相關(guān)文章

  • 劍指Offer(Java版) 持續(xù)更新中

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

    justCoding 評論0 收藏0
  • LeetCode 精選TOP面試題【51 ~ 100】

    摘要:有效三角形的個數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個數(shù)字。總結(jié)本題和三數(shù)之和很像,都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸,所以空間復(fù)雜度為 ...

    Clect 評論0 收藏0
  • 劍指offer--JavaScript版

    摘要:劍指在一個二維數(shù)組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。例如輸入前序遍歷序列和中序遍歷序列,則重建二叉樹并返回。其中負(fù)數(shù)用補(bǔ)碼表示。 本文為8月牛客網(wǎng)《劍指 offer》刷題做得,現(xiàn)整理出來作為參考。雖然是算法題,但本文用 JavaScript 編寫,看了《劍指 offer》以后發(fā)現(xiàn)很多問題處理的過程并不是最好的,所以本文僅供參考。以前全部代碼 A...

    MarvinZhang 評論0 收藏0
  • 劍指offer(javascript版)

    摘要:二維數(shù)組中的查找在一個二維數(shù)組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數(shù),輸入這樣的一個二維數(shù)組和一個整數(shù),判斷數(shù)組中是否含有該整數(shù)。例如輸入前序遍歷序列和中序遍歷序列,則重建二叉樹并返回。 1.二維數(shù)組中的查找 在一個二維數(shù)組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數(shù),輸入這樣的一個二維數(shù)...

    imtianx 評論0 收藏0
  • LeetCode 劍指 Offer 輪轉(zhuǎn)數(shù)組 轉(zhuǎn)旋轉(zhuǎn)字符串

    摘要:請定義一個函數(shù)實現(xiàn)字符串左旋轉(zhuǎn)操作的功能。比如,輸入字符串和數(shù)字,該函數(shù)將返回左旋轉(zhuǎn)兩位得到的結(jié)果。 目錄 第一題:左旋轉(zhuǎn)字符串 解題思路: 畫圖解析: 代碼實現(xiàn): 第二題:輪轉(zhuǎn)數(shù)組 解題思路: 畫圖解析: 代碼實現(xiàn): 第一題:左旋轉(zhuǎn)字符串 LeetCode 劍指 Offer 58: 描述:...

    Brenner 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<