Finden Sie minimale Peakelemente in einem Array

Question

Frage: Gegebene Array-Nummern $$a := [2, 7, 8, 5, 1, 6, 3, 9, 4]$$ Überprüfen Sie die folgenden Bedingungen, beide Bedingungen sollten erfüllt sein.

\ begin {versammeln} \ text {Wenn} ein [i]> ein [i-1] \ text {oder wenn das erste Element} ein [i]> ein [i + 1] \ end {sammeln}

\ begin {collect} \ text {If} a [i]> a [i + 1] \ text {oder if last element} a [LastIndex]> a [LastIndex - 1] \ end {collect}

• 1. Iteration - 8, 6, 9 sind Spitzenwerte.

  • Entfernen Sie das kleinste ele.
  • Entfernen Sie 6.
  • Neu arr {2, 7, 8, 5, 1, 3, 9, 4}.
  • Ausgabe Arr - {6}

• 2. Iteration - 8, 9 sind Spitzenwerte.

  • Entfernen Sie das kleinste ele.
  • Entfernen Sie 8.
  • Neu arr {2, 7, 5, 1, 3, 9, 4}.
  • Ausgabe Arr - {6, 8}

• 3. Iteration - 7, 9 sind Spitzenwerte.

  • Entfernen Sie das kleinste ele.
  • Entfernen Sie 7. Neu arr {2, 5, 1, 3, 9, 4}.
  • Ausgabe Arr - {6, 7, 8}

• 4. Iteration - 5, 9 sind Spitzenwerte.

  • Entfernen Sie das kleinste ele.
  • Entfernen Sie 5.
  • Neu arr {2, 1, 3, 9, 4}.
  • Ausgabe Arr - {6, 7, 8, 5}

• 5. Iteration - 2, 9 sind Spitzenwerte.

  • Entfernen Sie das kleinste ele.
  • Entfernen Sie 2.
  • Neu arr {1, 3, 9, 4}.
  • Ausgabe Arr - {6, 7, 8, 5, 2}

• 6. Iteration - 9 sind Spitzenwerte.

  • Entfernen Sie das kleinste ele.
  • Entfernen Sie 9.
  • Neu arr {1, 3, 4}.
  • Ausgabe Arr - {6, 7, 8, 5, 2, 9}

• 7. Iteration - 4 sind Spitzenwerte.

  • Entfernen Sie das kleinste ele.
  • Entfernen Sie 4.
  • Neu arr {1, 3}.
  • Ausgabe Arr - {6, 7, 8, 5, 2, 9, 4}

• 8. Iteration - 3 sind Spitzenwerte.

  • Entfernen Sie das kleinste ele.
  • Entfernen Sie 3.
  • Neu arr {1}.
  • Ausgabe Arr - {6, 7, 8, 5, 2, 9, 4, 3}

• 9. Iteration - 1 sind Spitzenwerte.

  • Entfernen Sie das kleinste ele.
  • Entfernen Sie 1.
  • Neu arr {1}.
  • Ausgabe Arr - {6, 7, 8, 5, 2, 9, 4, 3, 1}

Ausgabe: {6, 8, 7, 5, 2, 9, 4, 3, 1}

Meine Lösung funktioniert, aber ich suche nach einer optimierten Lösung. Lass es mich wissen, bitte.

Hier ist mein Code:

public int[] findMinimumPeaks(int[] arr){
        List<Integer> list1 = new ArrayList<Integer>(arr.length);
        int[] output = new int[arr.length];
        for(int i: arr)
            list1.add(i);
        
        for(int i =0; i<arr.length; i++){
            int minIndex = minimumPeakElement(list1);
            output[i] = list1.get(minIndex);
            list1.remove(minIndex);
        }
        return output;
    }
    
    public int minimumPeakElement(List<Integer> list1){
        int minIndex = 0, peakStart = Integer.MAX_VALUE, peakEnd = Integer.MAX_VALUE;
        int peak = Integer.MAX_VALUE, minPeak = Integer.MAX_VALUE;
        
        if(list1.size() >= 2){
            if(list1.get(0) > list1.get(1)) peakStart = list1.get(0);
            if(list1.get(list1.size() - 1) > list1.get(list1.size() - 2)) peakEnd = list1.get(list1.size() - 1);
            if(peakStart < peakEnd){
                minPeak = peakStart;
                minIndex = 0;
            }
            else if(peakEnd < peakStart){
                minPeak = peakEnd;
                minIndex = list1.size() - 1;
            }
        }
        
        for(int i=1; i<list1.size() - 1; i++){
            if(list1.get(i) > list1.get(i + 1) && list1.get(i) > list1.get(i-1)) peak = list1.get(i);
            if(peak < minPeak){
                minPeak = peak;
                minIndex = i;
            } 
        }
        return minIndex;
    }

```

Answer 1

Du sollst nicht bruteforce.

Ihr Algorithmus weist eine quadratische Zeitkomplexität auf und kann nicht gerettet werden. Du brauchst einen besseren.

Die erste Beobachtung, die Sie machen sollten, ist, dass beim Entfernen des Peaks andere Peaks gesetzt bleiben. Das allein reicht aus, um zu sehen, dass das erneute Scannen des gesamten Arrays Zeitverschwendung ist.

Eine wichtigere Beobachtung ist, dass nach dem Entfernen des Peaks der neue Peak möglicherweise nur an der Position unmittelbar neben dem zu entfernenden Peak angezeigt wird. Bitte beweisen Sie diese Tatsache (oder überzeugen Sie sich zumindest davon). Beachten Sie auch, dass der Neugeborenenpeak im Allgemeinen kleiner ist als die vorhandenen Peaks, falls vorhanden.

Ich hoffe es ist genug um dich zum Laufen zu bringen.

---

Wie für die richtige Überprüfung:

• Wohnung ist besser als verschachtelt. Der Zustand sollte list1.size() >= 2besser umgekehrt werden:

    if (list1.size() < 2) {
        // The list consists of a single element, which is a peak,
        // and it resides at index 0
        return 0;
    }
    // Proceed with a general case here
    ....
  

• list1sieht aus wie ein seltsamer Name. Es gibt keine anderen Listen, oder?

Answer 2

Ich habe einige Vorschläge für Ihren Code.

Fügen Sie loop& immer geschweifte Klammern hinzuif

Meiner Meinung nach ist es eine schlechte Praxis, einen Codeblock zu haben, der nicht von geschweiften Klammern umgeben ist. Ich habe in meiner Karriere so viele Fehler gesehen, die damit zusammenhängen. Wenn Sie vergessen, beim Hinzufügen von Code die geschweiften Klammern hinzuzufügen, brechen Sie die Logik / Semantik des Codes.

Extrahieren Sie den Ausdruck bei mehrfacher Verwendung in Variablen.

In Ihrem Code können Sie ähnliche Ausdrücke in Variablen extrahieren. Dadurch wird der Code kürzer und leichter lesbar. (java.util.List # size, java.util.List # get, ect)