arrays - कमह - एक सरणी को देखते हुए, क्या मैं ओ(एन) में सबसे लंबी सीमा में पा सकता हूं, जिसका अंतराल सीमा में सबसे बड़ा मूल्य है?




सर्वाधिक सीमाओं वाला देश कौन सा है (5)

एक साधारण ढेर आधारित समाधान। स्टैक होल्डिंग तत्वों (तकनीकी रूप से, इंडेक्स, लेकिन तुलना के लिए मूल्यों का उपयोग करें) के साथ बाएं से दाएं सरणी पर बाएं से ऊपर की ओर इटरेट करें जो या तो हैं:

  1. बाएं से सबसे बड़ा (यानी सरणी और तत्व की शुरुआत के बीच कोई बड़ा या बराबर तत्व नहीं)
  2. ढेर पर पिछले तत्व के बाद से सबसे बड़ा।

अगले तत्व x संसाधित करते समय, जब तक वे श्रेणी 2 से हैं, तब तक पॉप तत्व x से छोटे होते हैं, फिर स्टैक पर x दबाएं। जाहिर है, आपको वर्तमान अधिकतम को स्थिर समय में श्रेणी 2 और 1 के बीच समझने में सक्षम होना चाहिए।

उपरोक्त प्रसंस्करण ओ (एन) है - प्रत्येक तत्व को एक बार में धक्का दिया जा सकता है और अधिकतर बार पॉप किया जा सकता है। अंतिम ढेर होने के बाद, पड़ोसी जोड़े (ढेर पर) की जांच करें - जोड़े में से एक समाधान है। यह भी ओ (एन) है।

सरणी के पूरे स्कैन के बाद स्टैक (वसा आयत) पर रहने के साथ एक तस्वीर यहां दी गई है:

(उपर्युक्त तस्वीर में एक छोटी सी गलती है: बाईं ओर चौथी बार या तो पहले की तुलना में मोटी या कम खींची जानी चाहिए)

यह क्यों काम करता है: अंतिम स्टैक में इनपुट सरणी के सभी तत्व होते हैं जो किसी भी दो बड़े तत्वों के बीच नहीं होते हैं (मैंने दो बराबर तत्वों के बीच तत्व के मामले को छोड़ दिया है)। समाधान स्पष्ट रूप से ऐसे तत्वों की एक पड़ोसी जोड़ी है।

पायथन में एक कार्यान्वयन यहां दिया गया है:

from collections import namedtuple

E = namedtuple('E', 'i x')

def maxrange(iterable):
    stack = [E(0, None)]*2 # push sentinel values
    maxsofar = None

    top = lambda: stack[-1] # peek at the top element on the stack

    for i, x in enumerate(iterable):
        while top().x < x and top().x < maxsofar:
            stack.pop()
        stack.append(E(i, x)) # push
        maxsofar = max(maxsofar, x)

    return max(b.i-a.i for a,b in zip(stack, stack[1:]))

उदाहरण:

>>> maxrange([2,1,3])
2

पूर्णांक के दिए गए सरणी के लिए, 2 बिंदुओं (i और j) के बीच अधिकतम दूरी खोजें, जिनमें उनके बीच किसी भी तत्व की तुलना में उच्च मान हैं।

उदाहरण:

values: 0 10  8  9  6  7  4 10  0
index : 0  1  2  3  4  5  6  7  8 

समाधान के ऊपर के मानों के लिए i = 1, j = 7 है, लेकिन

  • अगर इंडेक्स 7 का मान 9 के बजाय 9 है तो समाधान i = 3, j = 7 है
  • अगर इंडेक्स 7 का मान 7 की बजाय 7 है तो समाधान i = 5, j = 7 है

मैं ओ (एन) में कोई समाधान नहीं देख सकता ... कोई भी?


मुझे यकीन नहीं है कि निम्न समाधान ओ (एन) है, लेकिन यह निश्चित रूप से 'लगभग ओ (एन)' है, और यह भी बहुत सरल है, कोड की कुछ पंक्तियां। यह निम्नलिखित अवलोकन पर आधारित है। इंडेक्स (i, j) की किसी भी जोड़ी के लिए, अंतराल [i, j] की मांग की गई संपत्ति होने पर उनके बीच एक चाप खींचें। अब देखें कि इन आर्कों को आकर्षित करना संभव है ताकि वे छेड़छाड़ न करें। फिर देखें कि सबसे छोटे जोड़े हैं (i, i + 1) - इनमें से सभी की मांग की गई संपत्ति है। इसके बाद, एक बड़ी जोड़ी हमेशा दो छोटे जोड़े के संकुचन द्वारा बनाई जा सकती है। इससे निम्नलिखित संरचना होती है: एक लिंक्ड सूची में जोड़े (i, i + 1) से शुरू करें। लिंक की गई सूची पर बार-बार जाएं, और लगातार लिंक अनुबंध करने का प्रयास करें। गैर-छेड़छाड़ की संपत्ति के कारण यह एल्गोरिदम ऑर्डर-इंडिपेंडेंट है। पर्ल कोड निम्नानुसार है।

#!/usr/local/bin/perl -w
use strict;

my @values    = (0, 10, 8, 9, 6, 7, 4, 10, 0);           # original example.
@values       = map { int(100 * rand()) } 1..100;        # random testing.
my $nvalues   = @values;
my @intervals = (1..$nvalues-1);       # this encodes a linked list 0->1, 1->2, N-2->N-1

my $change = 0;
my ($maxi, $maxj) = (0, 1);            # initial solution
my $maxdelta = 1;

do {
   my ($jstart, $j) = (0, $intervals[0]);
   $change = 0;
   while ($j < $nvalues-1) {
      my $jnext = $intervals[$j];
      while ($jnext < $nvalues -1 && $values[$j] == $values[$jnext]) {
          $jnext = $intervals[$jnext];   # lookahead to skip intervals with identical boundaries
      }
      if ($values[$j] < $values[$jstart] && $values[$j] < $values[$jnext]) {
         $intervals[$jstart] = $jnext;                   # contraction step
         print STDERR "contraction to $j $jnext\n";
         $change = 1;
         $j = $jnext;
         if ($jnext - $jstart > $maxdelta) {
            $maxdelta = $jnext - $jstart;
            ($maxi, $maxj) = ($jstart, $jnext);
         }
      }
      else {
         ($jstart, $j) = ($j, $intervals[$j]);
      }
   }
   print STDERR "---\n";
}
while ($change);


my $jstart = 0;

while ($jstart < $nvalues -1) {
   my $jnext = $intervals[$jstart];
   local $, = " ";
   print STDERR @values[$jstart..$jnext], "\n";
   $jstart = $jnext;
}

print STDERR "solution $maxi $maxj\n";

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



void Solution(const int* vData, int vLen) { typedef std::pair Interval; typedef std::vector ListaIntervaleType; ListaIntervaleType ListaIntervale;

/************************************************************************/ /* Get valid Intervals */ /************************************************************************/ #define IS_LAST_ELEM (i == vLen-1) int iIdxStart = -1; for (int i=1; i < vLen; ++i) { if (-1 == iIdxStart) { /* Searching for Interval START */ if (!IS_LAST_ELEM) { if (vData[i+1] < vData[i]) { iIdxStart = i; } } } else { /* Searching for Interval END */ if (vData[iIdxStart] <= vData[i] || IS_LAST_ELEM) { /* stop condition: crt val > start value*/ ListaIntervale.push_back(std::make_pair(iIdxStart,i)); if (!IS_LAST_ELEM && vData[i+1] < vData[i]) { iIdxStart = i; } else { iIdxStart = -1; } } } } /************************************************************************/ /* Concatenate intervals */ /************************************************************************/ //int iMaxLenIntervalIdx = -1; //int iMaxLenIntervalVal = 0; ListaIntervaleType::iterator crt; //for (crt=ListaIntervale.begin(); crt!=ListaIntervale.end(); crt++) //{ // ListaIntervaleType::iterator next = crt + 1; // if (next != ListaIntervale.end()) // { // if (crt->second == next->first) // { // if (crt->second < crt->first && // crt->second < next->second) // { // //concatenam // crt->second = next->second; // crt = ListaIntervale.erase(next); // } // } // } //} /************************************************************************/ /* Get Max */ /************************************************************************/ ListaIntervaleType::iterator solution = ListaIntervale.begin(); int iMaxLen = 0; for (crt=ListaIntervale.begin(); crt!=ListaIntervale.end(); crt++) { int iCrtLen = crt->second - crt->first; if (iCrtLen > iMaxLen) { iMaxLen = iCrtLen; solution = crt; } } /************************************************************************/ /* Print Solution */ /************************************************************************/ if (solution != ListaIntervale.end()) { wprintf(L"Solution idx=[%d-%d] val=[%d-%d]", solution->first, solution->second, vData[solution->first], vData[solution->second]); } else { wprintf(L"Solution NOT FOUND"); } return;

}


राफल्स समाधान अच्छा है, लेकिन हम ढेर के बिना कर सकते हैं और इसलिए कुछ स्मृति बचाओ। O(n) समय में एक छोटा और कुशल कार्यान्वयन यहां दिया गया है:

def highDist(seq):
    res, ltr, rtl = 0, 0, 0
    for i in range(len(seq)):
        if seq[i] >= seq[ltr]:
            res = max(res, i-ltr)
            ltr = i
        if seq[-i-1] >= seq[-rtl-1]:
            res = max(res, i-rtl)
            rtl = i
    return res

उदाहरण इनपुट पर चलाएं:

>>> print highDist([0, 10, 8, 9, 6, 7, 4, 10, 0])
6
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 9, 0])
4
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 7, 0])
2
>>> print highDist([])
0

चाल यह है कि अगर हमारे पास दो अंक हैं और b सेंट उनके बीच सबकुछ उनके से छोटा है, तो अधिकतम दूरी जिसे हम खोज रहे हैं, या तो |ba| या पूरी तरह से सीमा के बाहर। इसलिए यदि हम पूरे अनुक्रम को इस तरह विभाजित करते हैं, तो उनमें से एक वह सीमा है जिसे हम खोज रहे हैं।

हम विभाजन को आसानी से प्रत्येक छोर से एक परिणाम बना सकते हैं।


ईटीए: कुछ त्रुटियां मिली, क्षमा करें। काम के बाद मैं इस पर वापस आऊंगा, यह निश्चित रूप से एक दिलचस्प समस्या है।

छद्म कोड के प्रकार में लिखा; विचार सरणी पर तीन संख्याओं की एक खिड़की को स्थानांतरित करना और कुछ तुलना करना है, फिर तदनुसार अपने बाएं और दाएं पदों को अपडेट करें।

// Define the initial window
w1=a[0], w2=a[1], w3=a[2]
// Will hold the length of the current maximum interval
delta_max = 0

// Holds the value of the current interval's leftmost value
left=max(w1,w2,w3)
// Holds the position of the current interval's leftmost value
lpos= *position of the chosen wi above*

// Holds the position of the current interval's rightmost value
rpos = lpos + 1
// Holds the value of the current interval's rightmost value
right = a[rpos]

i = 0
// Holds the position of the max interval's leftmost value
lmax = 0
// Holds the position of the max interval's rightmost value
rmax = 0

while (i<n-3) do
    i = i + 3
    w1=a[i], w2=a[i+1], w3=a[i+2]

    if (w1<left) and (w2<left) and (w3<left)
        right = w3
        rpos = i + 2
    else
        // Set the new left to the first value in the window that is bigger than the current left
        if (w1>left): left = w1, lpos = i
        else
            if (w2>left): left = w2, lpos = i+1
            else
                if (w3>left): left = w3, lpos = i+2


    delta = rpos-lpos
    if delta>dmax: dmax = delta, lmax = lpos, rmax = rpos
    lpos = rpos
    rpos = lpos + 1
    right = a[rpos]
end





big-o