SPOJ ARRAYSUB: O (n) Komplexität Ansatz

Question

Ich habe versucht, diese Probleme auf SPOJ zu lösen http://spoj.pl/problems/ARRAYSUB

ich gelöst es zwei Ansätze

zunächst optimierte Brute-Force mit. Zweitens, Pivot bei k, 2k, 3k usw. nehmen und Maximum finden.

Obwohl beide Lösungen im ungünstigsten Fall akzeptiert werden, ist die Komplexität O (n * k);

Kann jemand vorschlagen, O (n) -Lösung Ansatz für die Probleme.

Unten ist mein Laufcode von Worst-Case-Komplexität O (n * k) angenommen:

#include<iostream> 
#include<cstdio> 
#include<climits> 
using namespace std; 
main() 
{ 
    long n; 
    cin >> n; 
    long *arr = new long[n]; 
    for(long i=0;i<n;i++) 
     cin >> arr[i]; 
    long k; 
    cin >> k; 
    long max=arr[0]; 
    for(long i=1;i<k;i++) 
    { 
     if(arr[i]>max) 
      max=arr[i]; 
    } 
    if(k!=n) 
    cout<<max<<" "; 
    else cout<<max; 
    for(long i=k;i<n;i++) 
    { 
     if(arr[i-k]==max) 
     {max=-1; 
     for(int j=i-k+1;j<=i;j++) 
     if(arr[j]>max) 
     max=arr[j]; 
     if(i!=n) 
     cout<<max<<" "; 
     else cout<<max; 

     } 
     else{ 
     if(arr[i]>max) 
     { max=arr[i]; 

     if(i!=n) 
     cout<<max<<" "; 
     else 
     cout<<max; 
     } 
     else 
     { 
     if(i!=n) 
     cout<<max<<" "; 
     else cout<<max;} 
     } 
    } 

     cout<<endl; 
    return(0); 
} 

Answer 1

Die Datenstruktur verwendet werden, um dieses Problem in O (n) zu lösen Zeit ist "Deque"

Eine natürliche Art und Weise würden die meisten Leute denken, ist zu versuchen, die Größe der Warteschlange die gleiche wie die Größe des Fensters zu halten. Versuchen Sie, sich von diesem Gedanken zu lösen und versuchen Sie, außerhalb der Box zu denken. Das Entfernen von redundanten Elementen und das Speichern von nur Elementen, die in der Warteschlange berücksichtigt werden müssen, ist der Schlüssel, um die effiziente O (n) -Lösung unten zu erreichen.

void maxInWindow(vector<int> &A, int n, int k, vector<int> &B) { 
    deque<int> Q; 
    for (int i = 0; i < k; i++) { 
    while (!Q.empty() && A[i] >= A[Q.back()]) 
     Q.pop_back(); 
    Q.push_back(i); 
    } 
    for (int i = k; i < n; i++) { 
    B[i-k] = A[Q.front()]; 
    while (!Q.empty() && A[i] >= A[Q.back()]) 
     Q.pop_back(); 
    while (!Q.empty() && Q.front() <= i-k) 
     Q.pop_front(); 
    Q.push_back(i); 
    } 
    B[n-k] = A[Q.front()]; 
    //B stores the maximum of every contiguous sub-array of size k  
} 

Erläuterung:

Die erste für die Schleife berechnet die maximal die ersten 'k' Elemente und Speichern des Index bei Q.front(). Dies wird zu B [0] = A [Index]. Der nächste Abschnitt, wir Push und Pop von der Rückseite, wenn A [i] größer als das vorherige Maximum gespeichert ist. Wir Pop von vorne wenn der Wert des Index ist kleiner als i-k, was bedeutet, dass es nicht mehr relevant ist.

Answer 2

Ein Ansatz, der effizienter als Brute Force ist, ist die Verwendung von Red Black Trees (RB) als Datenstruktur. Weil RB-Bäume die Eigenschaft haben, die in O (log n) -Zeit einfügen, entfernen und min oder max finden, wobei n die Anzahl der Knoten im Baum ist.

Obwohl AVL Trees die gleiche Eigenschaft hat, aber die Konstante hinter dem Big O ist groß im Vergleich zu RB Trees.

Die Gesamtkomplexität für das Problem wird jetzt O (n lg k).

Zuerst k Knoten in RB-Tree einfügen und dann find max verwenden, um das max-Element zu erhalten. (2 * log k) Zweitens entfernen wir das erste Element, das eingefügt wurde, und fügen dann ein neues Element ein und fragen dann nach dem max-Element. (3 * log k). Nach dem gleichen Verfahren benötigen wir ungefähr (3 * n * log k). Das ist O (n * log k).

Derzeit wird naive Brute-Force-Lösung nicht akzeptiert, aber diese Lösung wurde akzeptiert.