Finden Sie Spitzen in Array (mit Nachbarschaft)

Question

Angenommen, ich habe ein 1D-Array, und ich möchte Peaks finden. Der Unterschied zum klassischen Spitzenwert ist, dass ich nicht nur seine Nachbarn überprüfen muss, sondern auch n linke Nachbarn und n rechte Nachbarn. Zum Beispiel meine Array folgt:

[1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1]

Und n = 4. Ich muss jedes Unterfeld mit der Länge 4 + 1 + 4 überprüfen und sehen, ob das mittlere Element das Maximum ist.

Im Fall:

[5,6,7,8,9,8,7,6,5], 9 ist der Gipfel.

Aber das klingt nicht sehr effizient. Was kann eine bessere Lösung sein? Wenn ich einen Peak finde, kann ich die nächsten n Elemente ignorieren, denke ich.

Answer 1

Versuchen Sie, unwichtigen Vergleich zu vermeiden. Beispiel

public class NewClass12 { 
    static int [] arr = {1,2,3,4,5,3,2,1,0,9,7,6,5,4,3,2,1}; 
     public static void main(String [] args){ 
     int n = 4; //bounds 
     boolean peakFound = false; 
     int peak = 0; 
     //iterate of data 
     for(int k = n; k<=arr.length-n+1;k++){ 
      //check data within bounds 
      for (int i = 1;i <=n;i++){ 
       if(arr[k]<arr[k-i] || arr[k]<arr[k+i]){ 
       peakFound = false; 
       break; 
      } 
      else{ 
       peakFound = true; 
       peak = arr[k]; 
      } 
     } 
     if(peakFound) 
      System.out.println(peak); 
    } 
    } 
}