Spoj ARRAYSUB: हे (एन) जटिलता दृष्टिकोण

Question

मैं Spoj http://spoj.pl/problems/ARRAYSUB

मैं दो दृष्टिकोण

सबसे पहले अनुकूलित जानवर बल का उपयोग कर का उपयोग कर इसे हल पर इस समस्याओं को हल करने की कोशिश कर रहा था। दूसरी बार के, 2k, 3k पर पिवोट लेना और अधिकतम खोजना।

हालांकि दोनों समाधान सबसे खराब मामले में स्वीकार किए जाते हैं, जटिलता ओ (एन * के) होती है;

क्या कोई समस्या के लिए ओ (एन) समाधान दृष्टिकोण सुझा सकता है।

नीचे मेरी रनिंग स्वीकार किया जाता है सबसे ज्यादा मामले जटिलता हे की कोड (एन * ट):

#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

डेटा संरचना में हे (एन) इस समस्या को हल करने के लिए इस्तेमाल किया जा करने के लिए समय "Deque"

है

अधिकांश लोगों को लगता है कि कतार के आकार को खिड़की के आकार के समान बनाए रखने का एक प्राकृतिक तरीका है। इस विचार से दूर तोड़ने की कोशिश करें और बॉक्स के बाहर सोचने की कोशिश करें। अनावश्यक तत्वों को हटाकर और कतार में विचार करने वाले तत्वों को संग्रहीत करने के लिए नीचे कुशल ओ (एन) समाधान प्राप्त करने की कुंजी है।

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  
} 

स्पष्टीकरण:

पाश के लिए पहले Q.front में पहला 'k' तत्वों की अधिकतम गणना करता है और सूचकांक की दुकान()। यह बी [0] = ए [सूचकांक] बन जाता है। अगला अनुभाग, हम पीछे से धक्का और पॉप अगर ए [i] पिछले अधिकतम संग्रहीत से अधिक है। हम सामने से पॉप करते हैं यदि सूचकांक का मूल्य i-k से कम है जिसका अर्थ है कि यह अब और प्रासंगिक नहीं है।

Answer 2

ब्रूट फोर्स की तुलना में एक दृष्टिकोण जो लाल संरचना पेड़ (आरबी) डेटा संरचना के रूप में उपयोग करना है। चूंकि आरबी पेड़ों में ऐसी संपत्ति होती है जो ओ (लॉग एन) समय में न्यूनतम या अधिकतम को कम, हटाती है और पाते हैं जहां एन पेड़ में नोड्स की संख्या है।

हालांकि एवीएल पेड़ की एक ही संपत्ति है लेकिन बिग ओ के पीछे लगातार छिपा हुआ आरबी पेड़ की तुलना में बड़ा है।

समस्या के लिए समग्र जटिलता अब ओ (एन एलजी के) बन जाएगी।

आरबी ट्री में पहले सम्मिलित के नोड्स और फिर अधिकतम तत्व प्राप्त करने के लिए अधिकतम खोजें का उपयोग करें। (2 * लॉग के) दूसरा हम डालने वाले पहले तत्व को हटाते हैं और फिर एक नया तत्व डालें और फिर अधिकतम तत्व के लिए क्वेरी करें। (3 * लॉग के)। उसी प्रक्रिया के बाद, हमें लगभग (3 * एन * लॉग के) की आवश्यकता होती है। वह ओ (एन * लॉग के) है।

वर्तमान में बेवकूफ ब्रूट फोर्स समाधान स्वीकार नहीं किया जा रहा है लेकिन यह समाधान स्वीकार कर लिया गया है।