查找給定數組的一維峯值

我正在爲一維數組編寫峯值查找算法的代碼。我已閱讀此帖Peak finding algorithm。這正是我想要做的，有關時間複雜性的討論，但沒有任何僞代碼。問題：查找給定數組的一維峯值

給定一個數組[a,b,c,d,e,f,g]其中a到g是數字，b是一個高峯，當且僅當a<=b和b>=c。

示例：給定數組{1,2,3,4,5,19,25,20}，應返回索引6。的邊緣情況應該給：

{100,4,3,1,19,20} -- index 0

{1,3,5,19,20} -- index 4

我Java已經實現。我目前的運行時間是O(n)。我想知道這是否可以改進

public static int naive(int[] arr){ 
     int l=arr.length; 
     if (arr[0]>=arr[1]) { 
      return 0; 
     } 
     if (arr[l-1]>arr[l-2]){ 
      return l-1; 
     } 
     for (int i=1; i < arr.length-1;i++){ 
      if (arr[i] >= arr[i-1] && arr[i] >= arr[i+1]){ 
       return i; 
      } 
     } 
     return -1; 
    }

來源

2014-02-14 eagertoLearn

可以用除法進行編碼而治之算法，應該給'O（log n）的' –

@ user1988876：這將如何工作，我需要通過整個陣列來查找峯值。所以時間複雜度必須是'O（n）' – eagertoLearn

你有興趣找到一個峯值，而不是所有的峯值。 –

A binary search-like algorithm應該工作。這採用了divide and conquer策略。既然你對single peak感興趣，你可以做的最好的是O(log n)。但是如果你想找到所有的峯值，至少是O(n)。

這裏是divide-and conquer algorithm：

public static int peak1D(int[] arr, int start, int end){ 
      //edge cases 
     if (end-start==1){ 
      if (start==0) 
       return start; 
      else 
      return end; 
     } 
     int i = start+end>>>1; 
     if (arr[i]<arr[i-1]) 
      return peak1D(arr,start,i); 
     if (arr[i]<arr[i+1]){ 
      return peak1D(arr, i, end); 
     } 
     else 
      return i; 
    }

我有一對夫婦的投入測試，它似乎工作。我對邊緣案件的處理並不好。雖然這是簡單的推理

來源

2014-02-14 20:08:46

對不起，我不確定這是否可行。或者可能是我沒有清楚地理解它。你給我一個僞代碼，我可以嘗試嗎？ – eagertoLearn

@eagertoLearn：給我幾分鐘，我正在處理它 –

只有數字排序後才能進行二分搜索嗎？ – Marichyasana

以下函數可能比你更有效一點點。請注意，這會發現本地最大值。

public static int findLocalMaximum(int[] arr){ 
     int i = 0; 
     while(i + 1 < arr.length && arr[i+1] >= arr[i]) { 
      ++i; 
     } 
     return i; 
    }

編輯：以下函數找到問題中定義的峯值。請注意，我刪除了while循環中的邊界檢查，因爲只有在arr[l-2] > arr[l-1]時纔會到達循環，因此while循環中的條件將爲false，並且l-2將返回。

public static int findPeak(int[] arr){ 
     int l = arr.length; 
     if(arr[0] >= arr[1]) { 
      return 0; 
     } 

     if(arr[l-1] >= arr[l-2]) { 
      return l-1; 
     } 

     int i = 1; 
     while(arr[i+1] > arr[i]) { 
      ++i; 
     } 
     return i; 
    }

來源

2014-02-14 20:23:03 George

如果我可以提出我的解決方案：

public static int findPeak(int[] array, int start, int end) { 
    int index = start + (end - start)/2; 

    if (index - 1 >= 0 && array[index] < array[index - 1]) { 
     return findPeak(array, start, index - 1); 
    } else if (index + 1 <= array.length - 1 && array[index] < array[index + 1]) { 
     return findPeak(array, index + 1, end); 
    } else { 
     return array[index]; 
    } 
}

我認爲這是簡單直接，如果報表處理邊緣情形。我也測試了一些輸入，它似乎工作。

來源

2014-11-01 21:51:06

'start +（end - start）/ 2'可以簡化爲'（start + end）/ 2' – Roylee

假設數組是全局的，爲了簡單起見，您可以通過它，如果你想。

private static int getPeak1D(int start,int end) 
{ 
    int x = (start+end)/2; 

    if( (x == 0 && array[x] >= array[x+1]) || 
      (x == array.length-1 && array[x]>=array[x-1]) || 
      (x>0 && x< array.length-1 && array[x] >= array[x-1] && array[x] >= array[x+1])) 
     return x; 

    if(x+1 < array.length && array[x] < array[x+1]) 
     temp = getPeak1D(x+1,end); 

    if(temp > -1) 
     return temp; 

    if(x-1 > -1 && array[x] < array[x-1]) 
     return getPeak1D(0,x-1); 
    else 
     return -1; 
}

首先檢查峯的第一邊，第二邊和內部。如果沒有找到峯值，如果array [x + 1]> array [x]，則第二個if將進入數組的右半部分。我們將它存儲在臨時（我有它作爲全球）我們不會返回它，因爲在數組[X + 1]和數組[X-1]都大於數組[X]，但右側沒有找到任何峯，你應該去第三，如果檢查左側

檢查這對於其背後的邏輯 https://courses.csail.mit.edu/6.006/spring11/rec/rec02.pdf

來源

2017-08-21 18:52:43

查找給定數組的一維峯值

回答

相關問題