webentwicklung-frage-antwort-db.com.de

Finden Sie lokale Minima in einem Array

Bestimmen Sie für ein Array von Ganzzahlen die lokalen Minima. Ein Element A [i] ist als lokales Minimum definiert, wenn A [i-1]> A [i] und A [i] <A [i + 1] gilt, wobei i = 1 ... n-2 ist. Bei Begrenzungselementen muss die Anzahl nur kleiner als die angrenzende Zahl sein.

Ich weiß, wenn es nur ein lokales Minimum gibt, können wir es mit modifizierter binärer Suche lösen. Wenn es jedoch bekannt ist, dass mehrere lokale Minima im Array vorhanden sind, kann es in O(log n) time gelöst werden?

27
devsda

Wenn die Unterscheidbarkeit der Array-Elemente nicht garantiert ist, ist dies in O (log n) nicht möglich. Der Grund dafür ist folgender: Angenommen, Sie haben ein Array, in dem alle n> 1 Werte gleich sind. In diesem Fall kann keines der Elemente ein lokales Minimum sein, da kein Element kleiner ist als seine Nachbarn. Um jedoch festzustellen, dass alle Werte gleich sind, müssen Sie sich alle Array-Elemente ansehen, was O(n) Zeit in Anspruch nimmt. Wenn Sie weniger als O(n) verwenden, können Sie nicht unbedingt alle Array-Elemente anzeigen.

Wenn andererseits garantiert ist, dass die Array-Elemente unterschiedlich sind, können Sie dies in O (log n) -Zeit unter Verwendung der folgenden Beobachtungen lösen:

  1. Wenn es nur ein Element gibt, ist es garantiert ein lokales Minimum.
  2. Wenn es mehrere Elemente gibt, sehen Sie sich das mittlere Element an. Wenn es ein lokales Minimum ist, sind Sie fertig. Andernfalls muss mindestens eines der Elemente daneben kleiner sein. Stellen Sie sich nun vor, was passieren würde, wenn Sie an einem der kleineren Elemente beginnen und schrittweise zu einem der Enden des Arrays in der Richtung vom mittleren Element weg gehen. Bei jedem Schritt ist entweder das nächste Element kleiner als das vorherige oder es wird größer. Schließlich werden Sie entweder auf diese Weise das Ende des Arrays erreichen oder ein lokales Minimum erreichen. Beachten Sie, dass dies bedeutet, dass Sie könnte tun, um ein lokales Minimum zu finden. Das werden wir aber eigentlich nicht tun. Stattdessen verwenden wir die Tatsache, dass in dieser Hälfte des Arrays ein lokales Minimum vorhanden ist, als Rechtfertigung für das Wegwerfen einer Hälfte des Arrays. In den verbleibenden Resten finden wir garantiert ein lokales Minimum.

Folglich können Sie den folgenden rekursiven Algorithmus aufbauen:

  1. Wenn es nur ein Array-Element gibt, handelt es sich um ein lokales Minimum.
  2. Wenn es zwei Array-Elemente gibt, überprüfen Sie jedes. Man muss ein lokales Minimum sein.
  3. Ansonsten sehen Sie sich das mittlere Element des Arrays an. Wenn es sich um ein lokales Minimum handelt, geben Sie es zurück. Andernfalls muss mindestens ein benachbarter Wert kleiner als dieser sein. Verwenden Sie die Hälfte des Arrays, das dieses kleinere Element enthält (nicht jedoch die Mitte).

Beachten Sie, dass dies die Wiederholungsbeziehung hat

T (1) ≤ 1

T (2) ≤ 1

T (n) ≤ T (n/2) + 1

Mit dem Hauptsatz können Sie zeigen, dass dieser Algorithmus nach Bedarf in der Zeit O (log n) abläuft.

Hoffe das hilft!

Bitte beachten Sie auch, dass dieser Algorithmus nur funktioniert, wenn Kanten des Arrays als lokale Minima gelten, wenn sie kleiner als das benachbarte Element sind.

59
templatetypedef

Die Anzahl der lokalen Minima kann n/2 sein. Sie können sie nicht alle in O(log n) auflisten.

6
foxcub

Verwenden Sie einen Divide-and-Conquer-Algorithmus. Sei m = n/2 und untersuche den Wert A [m] (thatis, das Element in der Mitte des Arrays).

Fall 1: A [m - 1] <A [m]. Dann muss die linke Hälfte des Arrays ein lokales Minimum enthalten, also auf der linken Hälfte erneut suchen. Das können wir durch Widerspruch zeigen: Nehmen Sie an, dass A [i] kein lokales Minimum für jedes 0 ≤ i <m ist. Dann ist A [m-1] kein lokales Minimum, was impliziert, dass A [m-2] <A [m-1] ist. In ähnlicher Weise ist A [m - 3] <A [m - 2]. Weiter auf diese Weise erhalten wir A [0] <A [1]. Aber dann ist A [0] ein lokales Minimum, entgegen unserer ursprünglichen Annahme.

Fall 2: A [m + 1]> A [m]. Dann muss die rechte Hälfte des Arrays ein lokales Minimum enthalten, also Auf der rechten Hälfte. Dies ist symmetrisch zu Fall 1.

Fall 3: A [m - 1]> A [m] und A [m + 1] <A [m]. Dann ist A [m] ein lokales Minimum, also geben Sie es zurück. Die Laufzeitwiederholung ist T(n) = T(n/2) + Θ (1), was T(n) = Θ (log n).

5
Elad

Tatsächlich kann mein vorheriger Algorithmus modifiziert werden, um alle Maxima in O (log n) Zeit zu erhalten. Ich habe getestet, dass es für alle Eingaben gut funktioniert. Bitte lassen Sie mich Ihr Feedback wissen

public class LocalMaximas {

@Test
public void test () {
    System.out.println("maximas: please modify code to handle if array size is <= 2");

    int []a = {5,8,10,25,6,3,44,51,55,56,57,58,34,5,59,2};
    localMaximas(a);

    int []b = {9,7,2,8,5,6,3,4, 2}; //9,8,6,4
    localMaximas(b);

    int [] c= {15, 13, 12, 18, 19, 20, 7, 6, 5, 4, 3, 2, 1};//15,20
    localMaximas(c);
}

public  void localMaximas (int [] a) {
    System.out.println("\n\n");
    if(isMaxima(a,0)) {
        System.out.println(a[0]);
    }
    if(isMaxima(a,a.length-1)) {
        System.out.println(a[a.length-1]);
    }
    localMaximas(a,0,a.length-1);
}

int localMaximas(int []a,int low, int high) {
    int mid = (low+high)/2;
    if(high-low > 3) {     // more than 4 items in currently  divided array
        if(isMaxima(a,mid)) {
            System.out.println(a[mid]);
        }   
        localMaximas(a,low, mid);
        localMaximas(a,mid, high);
    }
    else if(high-low == 3){ //exactly 4 items in currently  divided array
        localMaximas(a,low, mid+1);
        localMaximas(a,mid, high);
    }   
    else if((high-low == 2) && (isMaxima(a,low+1))) {
        System.out.println(a[low+1]);
    }
    return 0;
}

int maxof(int []a, int i, int j) {
    if(a[i] <a[j]) {
        return j;
    }
    else {
        return i;
    }
}

boolean isMaxima(int []a ,int mid) {
    if(mid == 0) {
        if(maxof(a, mid, mid+1) == mid) {
            return true;
        }
        else {
            return false;
        }
    }
    else if(mid==a.length-1) {
        if(maxof(a,mid,mid-1) == mid) {
            return true;
        }
        else {
            return false;
        }
    }
    else {
        if((maxof(a, mid, mid+1) == mid) && (maxof(a, mid, mid-1) == mid)) {
            return true;
        }
        else {
            return false;
        }           
    }
}
}
0
Sohan

Die ursprüngliche Frage ist nicht vollständig.

Die vollständige Frage und die ausführlichere Erklärung finden Sie unter Lokale Minima in einem Array suchen ! - nicht mein Blog

Bestimmen Sie in einem Array eindeutiger Ganzzahlen, deren erste beiden Zahlen abnehmen und die letzten beiden Zahlen zunehmen, eine Zahl in dem Array, die lokale Minima ist. Eine Zahl im Array wird als lokales Minimum bezeichnet, wenn sie kleiner als die linke und rechte Zahl ist. 

Zum Beispiel ist in der Anordnung 9, 7, 8, 5, 6, 6, 4, 2 ein lokales Minimum, da es kleiner als seine linke und rechte Zahl 7 und 8 ist. In ähnlicher Weise ist 5 ein anderes lokales Minimum liegt zwischen 8 und 6, beide größer als 5. 

Sie müssen eines der lokalen Minima finden.

0
jeffery.yuan

Ihr Algorithmus funktioniert für dieses Array nicht 

15, 13, 12, 18, 19, 20, 7, 6, 5, 4, 3, 2, 1

Hier ist das lokale Minimum 12 .., aber wenn ich das mittlere Element, also 7, überprüfe, wird Ihr Algorithmus die linke Hälfte (die das Minimum hat) verwerfen und die rechte Hälfte überprüfen. Daher funktioniert es nicht

Ich denke, es wird nur für den Sonderfall funktionieren, wenn das Array eine besondere Eigenschaft hat: A [1] ≥ A [2] und A [n - 1] ≤ A [n]. 

0
user2316569

Hier ist eine Lösung, die mit O (log n) funktioniert. Grundsätzlich funktioniert dies beim Merge-Sort-Ansatz (Dividieren und Erobern).

public class LocalMaxima {
    int []a = {5,8,10,25,6,3,44,51,55,56,57,58,34,5,59};

    @Test 
    public  void localMaxima () {
        System.out.println((a[localMaxima(0,a.length-1)]));
    }

    int localMaxima(int low, int high) {
        if(high-low > 2) {
            int mid = (low+high)/2;
            return maxof(localMaxima(low,mid),localMaxima(mid+1, high));
        }
        else if(high-low == 1) {
            return maxof(high,low);
        }
        else if(high-low == 0) {
            return high;
        }
        if(high-low == 2) {
            return maxof(maxof(low, high),low+1);
        }
        return 0;
    }

    int maxof(int i, int j) {
        if(a[i] <a[j]) {
            return j;
        }
        else {
            return i;
        }
    }
}
0
Sohan