[[409450]]

本文轉(zhuǎn)載自微信公眾號(hào)「神奇的程序員K」，作者神奇的程序員K。轉(zhuǎn)載本文請(qǐng)聯(lián)系神奇的程序員K公眾號(hào)。

前言

把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，就稱之為數(shù)組的旋轉(zhuǎn)。有一個(gè)遞增排序數(shù)組，將其開(kāi)頭的若干個(gè)元素移動(dòng)至數(shù)組的末尾，尋找其中的最小值。

本文就跟大家分享下如何用最快的速度找到遞增旋轉(zhuǎn)數(shù)組中的最小值，歡迎各位感興趣的開(kāi)發(fā)者閱讀本文。

實(shí)現(xiàn)思路

乍一看這個(gè)問(wèn)題，一部分開(kāi)發(fā)者首先想到的解法就是從頭到尾遍歷下數(shù)組，這樣就能找出最小的元素。這種思路的時(shí)間復(fù)雜度是O(n)，沒(méi)有將題目中的條件利用起來(lái)，因此這種方案不是本題的正確答案。

舉例分析

接下來(lái)，我們來(lái)分析下題目，通過(guò)舉例、觀察來(lái)尋找突破口。我們先來(lái)列舉一個(gè)遞增數(shù)組。

如上圖所示，我們準(zhǔn)備了一個(gè)1 ～ 5的遞增數(shù)組，然后將其開(kāi)頭的兩個(gè)元素搬到了數(shù)組的末尾，這樣就構(gòu)成了一個(gè)旋轉(zhuǎn)數(shù)組。

經(jīng)過(guò)一番觀察后，我們可以發(fā)現(xiàn)：

• 旋轉(zhuǎn)后的數(shù)組可以劃分為兩個(gè)已經(jīng)排序的小數(shù)組
• 前面子數(shù)組的元素都大于等于后面子數(shù)組的元素
• 最小的數(shù)字是這兩個(gè)子數(shù)組的分界線

二分查找

經(jīng)過(guò)上面的分析，我們可知旋轉(zhuǎn)后的數(shù)組在一定程度上是排好序的，因此我們可以嘗試使用二分查找的思路來(lái)尋找最小的元素。

接下來(lái)，我們準(zhǔn)備兩個(gè)指針(左指針、右指針)，左指針指向數(shù)組的第一個(gè)元素，右指針指向數(shù)組的末尾元素，如下圖所示：

觀察上圖后，我們發(fā)現(xiàn)它們的中間元素是5、最小值在5的后面，因此我們就可以排除中間值之前的元素了，移動(dòng)左指針至5，如下圖所示：

此時(shí)，它們的中間元素是1，我們發(fā)現(xiàn)最小值2的前面，因此我們就可以將右指針移動(dòng)至中間1，如下所所示：圖片

最后，我們發(fā)現(xiàn)左指針與右指針相鄰，右指針指向的元素正好是旋轉(zhuǎn)數(shù)組的最小元素。

經(jīng)過(guò)上述畫(huà)圖分析后，我們可以得到如下規(guī)律：

• 如果兩個(gè)指針的中間元素大于等于左指針指向的元素，那么最小值一定在中間元素的后面，移動(dòng)左指針至中間值位置縮小查找范圍
• 如果兩個(gè)指針的中間元素小于等于右指針指向的元素，那么最小值一定在中間元素的前面，移動(dòng)右指針至中間值位置縮小查找范圍
• 左指針一定指向前面的遞增子數(shù)組，右指針一定指向后面的遞增子數(shù)組
• 當(dāng)左、右指針相鄰時(shí)，右指針?biāo)赶虻脑鼐褪沁@個(gè)數(shù)組的最小值

時(shí)間復(fù)雜度分析：每次移動(dòng)指針，查找范圍都會(huì)縮小到原先的一半，因此總的時(shí)間復(fù)雜度為O(logn)

特殊情況

上述規(guī)律可以滿足大多數(shù)情況，當(dāng)出現(xiàn)下述情況時(shí)我們就不能采用二分查找了：

• 當(dāng)數(shù)組的0號(hào)元素小于最后一個(gè)元素時(shí)，證明這個(gè)數(shù)組是排好序的，它的最小值是數(shù)組的第0號(hào)元素
• 當(dāng)左指針與右指針指向的元素相同且它們的中間元素也與其相同，那么就只能使用順序查找，如下圖所示：

實(shí)現(xiàn)代碼

接下來(lái)，我們根據(jù)上述所講內(nèi)容來(lái)總結(jié)下思路：

• 判斷數(shù)組是否已經(jīng)排好序(第一個(gè)元素是否小于最后一個(gè)元素)
• 左指針指向的值大于等于右指針指向的值就根據(jù)條件移動(dòng)左、右指針：
  • 循環(huán)終止條件：左指針與右指針相鄰
  • 求左、右指針的中間索引
  • 左指針指向的值與右指針指向的值相同且中間元素也與之相同(使用順序查找 )
  • 中間值大于等于左指針指向的值，移動(dòng)左指針位置至中間值位置
  • 中間值小于等于右指針指向的值，移動(dòng)右指針位置至中間值位置
• 循環(huán)結(jié)束，返回最小值

代碼如下所示：

// 把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。 
// 輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。 
// 例如，數(shù)組[3，4，5，1，2]為[1，2，3，4，5]的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。 
 
export default class FindWhirlingArrayMinVal { 
  private leftPointer; 
  private rightPointer; 
  private middleIndex; 
 
  constructor() { 
    this.leftPointer = 0; 
    this.rightPointer = 0; 
    this.middleIndex = 0; 
  } 
 
  public getMinValue(incrementArray: Array<number>): number { 
    this.rightPointer = incrementArray.length - 1; 
    // 第一個(gè)元素小于最后一個(gè)元素，證明數(shù)組是排好序的 
    if (incrementArray[this.leftPointer] < incrementArray[this.rightPointer]) { 
      // 其最小值為第一個(gè)元素 
      return incrementArray[this.leftPointer]; 
    } 
    while ( 
      incrementArray[this.leftPointer] >= incrementArray[this.rightPointer] 
    ) { 
      // 循環(huán)終止條件: 右指針與左指針相鄰，最小值為右指針?biāo)赶虻闹?nbsp;
      if (this.rightPointer - this.leftPointer === 1) { 
        this.middleIndex = this.rightPointer; 
        break; 
      } 
      // 求中間值 
      this.middleIndex = Math.floor((this.leftPointer + this.rightPointer) / 2); 
      // 左指針指向的值與右指針指向的值相同且中間元素也與之相同 
      // 則無(wú)法使用二分查找，需要順序查找 
      if ( 
        incrementArray[this.leftPointer] === 
          incrementArray[this.rightPointer] && 
        incrementArray[this.middleIndex] === incrementArray[this.leftPointer] 
      ) { 
        // 按順序查找 
        let minValue = incrementArray[0]; 
        for (let i = 0; i < incrementArray.length; i++) { 
          if (incrementArray[i] < minValue) { 
            minValue = incrementArray[i]; 
          } 
        } 
        return minValue; 
      } 
 
      if ( 
        incrementArray[this.middleIndex] >= incrementArray[this.leftPointer] 
      ) { 
        // 中間值大于等于左指針指向的值 
        // 移動(dòng)左指針至中間值位置 
        this.leftPointer = this.middleIndex; 
      } else if ( 
        incrementArray[this.middleIndex] <= incrementArray[this.rightPointer] 
      ) { 
        // 中間值小于等于右指針指向的值 
        // 移動(dòng)右指針至中間值位置 
        this.rightPointer = this.middleIndex; 
      } 
    } 
    // 循環(huán)結(jié)束，返回最小值 
    return incrementArray[this.middleIndex]; 
  } 
} 

完整代碼請(qǐng)移步：findWhirlingArrayMinVal-test.ts