山峰陣列中的峰指數


難度級別 容易獎學金
經常問 Microsoft微軟
排列 二元搜尋

什麼是山峰陣列問題中的峰指數?

數組可以說是 山陣 如果顯示以下屬性:

  1. 給定數組的長度應大於或等於3 長度> = 3.
  2. 陣列中只能有一個峰或最大元素。
  3. 它應該遵循:ARRAY [0] <ARRAY [1] <ARRAY [i-1] <ARRAY [i]> ARRAY [i + 1]> ARRAY [..]> ARRAY [length-1]

我們的任務是找到山峰指數 排列.

輸入

[10,20,30,20,10]

產量

2

解釋

指數 “2”“30” 具有最大的價值。

山峰陣列中的峰指數

輸入

[0,2,1,0]

產量

1

解釋

指數 “1”“2” 具有最大的價值。

算法

  1. 設置為低到0。
  2. 將數組的長度設置為高減去-1。
  3. 聲明一個可變的中點。
  4. 設置中=低+(高–低)/ 2。
  5. 從低到高:
    1. 如果array [mid]> = array [mid + 1]。
      1. 那麼高=中。
    2. 其他
      1. 然後低=中+ 1。
  6. 返回低。

解釋

因此,我們必須在給定數組中找到峰值索引。 為此,我們將使用 二進制搜索 接近一點。 我們在名為getPeakIndex的代碼中有函數聲明,在其中傳遞輸入數組和數組的長度。

我們聲明一個中位數並初始化為0,高等於高-1,我們將打開一個 while循環 它將持續到虛假低<高的條件為止。 進入循環,我們設置mid = low +(high-low)/ 2。

我們的輸入值為:{4,8,16,32,27,9,3};

因此high的值將是數組長度-1 => 7 – 1 = 6

高= 6

低= 0

中=低+(高-低)/ 2 => 0 +(6 – 0)/ 2 = 3

中= 3。

現在如果((array [mid]> = array [mid + 1])

也就是說,如果32大於或等於27,則條件將為true,並將其設置為high = mid

所以現在低= 0,

高= 3,

中= 3;

中=低+(高-低)/ 2 => 0 +(3 – 0)/ 2 = 1

中= 1。

現在它將檢查是否(array [mid]> = array [mid + 1])

即8大於或等於16,條件將為假並執行else部分並設置為low = mid +1;

所以現在低= 2,

高= 3,

中= 1;

中=低+(高-低)/ 2 => 2 +(3 – 2)/ 2 = 2

中= 2。

現在它將檢查是否(array [mid]> = array [mid + 1])

即16大於或等於32,條件將為假並執行else部分並設置為low = mid +1;

所以現在低= 3,

高= 3,

中= 3;

在這裡,當它循環而(低<高)時,表示3 <3,這是錯誤的

並退出循環並返回低電平,即low = 3。

輸出將變為:

峰值指數是:3

用C ++實現

#include <iostream>
using namespace std;

int peakIndex(int arr[],int high)
{
    int low=0;
    int mid;
    high-=1;
    while( low < high )
    {
        mid = low +(high - low)/2;
        if(arr[mid]>=arr[mid+1])
        {
            high=mid;
        }
        else
        {
            low=mid+1;
        }
    }
    return low;
}
int main()
{
    int mountainArray[]= {4,8,16,32,27,9,3};
    int n = sizeof(mountainArray)/sizeof(mountainArray[0]);
    int peak=peakIndex(mountainArray,n);
    cout<<"Peak index is:"<<peak;
    return 0;
}
Peak index is:3

用Java實現

class peakIndex {
  public static int getPeakIndex(int[] array) {
    int low = 0;
    int high = array.length - 1;
    int mid;
    while (low<high) {
      mid = low + (high - low) / 2;
      if (array[mid] >= array[mid + 1]) {
        high = mid;
      } else {
        low = mid + 1;
      }
    }
    return low;
  }

  public static void main(String[] args) {
    peakIndex pi = new peakIndex();
    int mountainArray[] = { 4, 8, 16, 32, 27, 9, 3 };
    int peak = getPeakIndex(mountainArray);
    System.out.println("Peak index is:" + peak);
  }
}
Peak index is:3

複雜度分析

時間複雜度

O(log n) 其中n是數組的長度。

空間複雜度

O(1) 因為我們不使用任何額外的或輔助的空間進行評估。

參考