Monotonic-Pair - Codility

Ich war gerade bei Codility, und lief in eine Aufgabe, für die ich nicht finden können, eine Lösung im gezielten O(n) Effizienz; meine Lösung läuft in O(n2). Ich würde mich sehr freuen, wenn jemand nur mir einen Tip geben, wie man es schneller laufen. Hier ist die Aufgabe.

Eine nicht-leere null-indiziert Ein array aus N ganzen zahlen gegeben ist.

Einen monotonic_pair ist ein paar ganzer zahlen (P, Q), so dass 0 ≤ P ≤ Q < N und A[P] ≤ A[Q].

Das Ziel ist, zu finden, die monotonic_pair, deren Indizes sind am weitesten auseinander. Genauer gesagt, sollten wir maximieren den Wert Q − P. Es ist ausreichend zu finden, nur der Abstand.

Betrachten Sie beispielsweise Ein array mit:

A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2

Gibt es elf monotonic_pairs: (0,0), (0, 2), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (3, 4), (4, 4), (5, 5). Der größte Abstand beträgt 3, im paar (1, 4).

Schreiben Sie eine Funktion:

Klasse Lösung { public int Lösung(int[] A); }

dass, da eine nicht-leere null-indizierten array A von N ganzen zahlen, gibt die größte Distanz innerhalb der monotonic_pairs.

Beispiel:

A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2

die Funktion zurückgeben sollte 3, wie oben erläutert.

Davon ausgehen, dass:

N ist eine ganze Zahl im Bereich [1..300,000];
jedes element von array A ist eine ganze Zahl im Bereich [-1,000,000,000..1,000,000,000].
Komplexität:

erwartete worst-case Zeitkomplexität ist O(N);
erwartete worst-case-Raum-Komplexität ist O(N), über die Eingabe-Speicher (nicht mitgerechnet den benötigten Speicher für die input-Argumente).
Die Elemente des Eingabe-arrays geändert werden kann.

Und meine 1. Idee, Lösung (läuft in O(n2)):

    public static int solution(int[] A) {
    int max = 0;
    for(int i=0; i<A.length-1; i++) {
        for(int j=i+1; j<A.length; j++) {
            if(A[j] >= A[i] &&
                    (j - i) >= max) {
                max = j - i;
            }
        }
    }
    return max;
}

Die gleiche Idee kann verwendet werden, ist hier beschrieben: stackoverflow.com/questions/22233018/...
Auch der gleiche Algorithmus 🙁

InformationsquelleAutor Whizzil | 2014-04-16

algorithm java

Erstellen Sie ein temporäres array mit maximalen Werten in absteigender Reihenfolge:

int[] top = new int[A.length];
int max = -Integer.MAX_VALUE;
for (int i=A.length-1; i>=0; i--) {
    if (A[i] > max) max = A[i];
    top[i] = max;
}

so können Sie schnell finden Sie mit binäre Suche:

int find(int[] t, int min) {
    int s = 0;
    int e = t.length-1;

    if (t[e] >= min) return e;

    while (true) {
        int x = (s+e) / 2;
        if (x == t.length-1) return t.length-1;
        if (t[x] >= min && t[x+1] < min) return x;

        if (t[x] < min) e = x;
        else s = x;
    }
}

Und man hat eine Lösung:

int best = 0;
for (int i=0; i<A.length; i++) {
    int c = find(top, A[i]) - i;
    if (c > best) best = c;
    if (best >= A.length-i) return best;
}

return best;

InformationsquelleAutor MarcinLe

MarcinLe ist besser als n^2, aber läuft immer noch in nlogn. Sie optimieren können, indem Sie nicht tun, Ihre logn-lookup jedes mal. Stattdessen Durchlaufen nach vorne über Ihre max-Arrays und Ihre Eingabe Ein [] - array an der gleichen Zeit garantieren die lineare Zeit.

int[] top = new int[A.length];
int max = -Integer.MAX_VALUE;
for (int i=A.length-1; i>=0; i--) {
    if (A[i] > max) max = A[i];
    top[i] = max;
}

int best = 0;
int curMaxIndex = 0;
for (int i=0; i<A.length; i++) {
    while(curMaxIndex < top.length && top[curMaxIndex] >= A[i])
        curMaxIndex++;
    if((curMaxIndex - 1 - i) > best)
        best = curMaxIndex - 1 - i
}

return best;

InformationsquelleAutor Phil Anderson

Es ist auch ein weiterer Algorithmus, basiert auf der Suche nach maximaler Abstand zwischen den Paaren (sorry, PHP), hat es auch O(n2) Komplexität:

function solution($a) {

    $length = count($a);

    for($max = $length-1; $max > 0; $max-- ) {
        for($i = 0; $i < $length - $max ; $i++) {
            if ($a[$i] <= $a[$i+$max]) {
                return $max;
            }    
        }
    }

    return 0;
}

InformationsquelleAutor pliashkou

0

Ich denke, Sie haben zu denken, in Bezug auf Distanz. Es ist wie die Breite-zuerst-Suche. Suchen Sie nach all den Pärchen, die haben der maximale Abstand ( die Größe des Arrays ), dann diejenigen mit Abstand 1 und so weiter. Ich arbeite dran und werde versuchen zu kommen mit einer c++ - Lösung.
- Das ist manchmal schnell, aber n^2 im schlimmsten Fall. Denken, was passieren würde, auf [5,4,3,2,1]. Es würde Blick auf jede mögliche combo vor der Rückkehr length-1.
InformationsquelleAutor Bruno Gallien

Stieß ich auf die ähnlichen test und entschied, es zu lösen in C.
Ich glaube, dass meine Lösung läuft als O(nlog(n)), worst-case und O(1) - im besten Fall.
Jetzt habe ich mit O(1) lose, aber es ist sehr gut möglich.

Grundsätzlich arbeitete ich mit 2 Zeigern. Man bewegt sich langsam vom Heck des Arrays, und ein scan gegen jede gefunden vom Kopf. Ich habe sofort brechen aus der Schleife auf die Paare, deren Indizes sind am weitesten auseinander, die passieren, werden zuerst berechnet mit dieser Methode.

O(1) möglich wird, weil wenn der erste monotonic-pair-Mädchen, die Sie berechnen, passiert am Ende zu sein und der Kopf der Liste, dann ist Ihre Antwort. Es gibt keinen möglichen Wert größer, dann wird dies wieder.

int solution(int A[], int N) {
    //write your code in C90
    int p,q;
    //forward and backwards iterators
    int fi,bi=N-1;
    //track largest difference
    int diff=0;

    //interate through entire loop
    for(; bi >= 0; --bi){
       //Initialization
       p=q=bi;
       fi=0;

       //looking from the front
       for(fi=0; fi<bi; fi++){
          if(A[fi] <= A[p] && A[q] >= A[fi] && fi<bi){
             p=fi;
             break;
          }
       }
       if(diff < (q-p)){
          diff = (q-p);
       }

       if(diff >= bi){
          break;
       }
    }
    return diff;
}

InformationsquelleAutor Chris

Meine Lösung Aber hab 66%. Seiner O(n**2) Zeit-Komplexität. Code ist in JavaScript.

function solution(A) {
    var N = A.length;
    var distance = 0;
    for(var i = 0; i < N-1; i++) {
        for(var j = i; j < N; j++){            
            if(A[i] <= A[j]  && (j - i) > distance)
                distance = j - i;
        }
    }
    return distance;
}

InformationsquelleAutor Durgaprasad Budhwani

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.