एक विस्तृत सरणी

Question

साक्षात्कार प्रश्न की औसत का ट्रैक रखते हुए:

नीचे संपादित आप एक सरणी दिया जाता है। आप इसमें से 2 ढेर, एक मिनीहेप और अन्य अधिकतम ढेर बनाते हैं। अब O (nlog n) समय में इन 2 प्रदान किए गए ढेर का उपयोग करके सरणी का औसत खोजें।

सही प्रश्न संख्या यादृच्छिक रूप से जेनरेट की जाती है और एक (विस्तार) सरणी में संग्रहीत होती है। आप मध्यस्थ का ट्रैक कैसे रखेंगे?

समाधान इस समस्या को 2 ढेर का उपयोग करके हल किया जा सकता है और औसत हमेशा ओ (1) समय में उपयोग किया जा सकता है।

Answer 1

एक ढेर से पॉपिंग एक ओ (लॉग एन) ऑपरेशन है, इसलिए आप ढेर में से आधे तत्वों को पॉप करके और अंतिम पॉपड वैल्यू ले कर ओ (एन लॉग एन) प्राप्त कर सकते हैं (आपको संभालना होगा किनारे के मामलों)। हालांकि यह अन्य ढेर का लाभ नहीं लेता है।

आप selection algorithm का उपयोग कर ओ (एन) प्राप्त कर सकते हैं, लेकिन निरंतर कारक बहुत अधिक है। यदि आपके पास पहले से ही ढेर है तो पूर्व सुझाव शायद बेहतर है।

Answer 2

यहां आप दोनों ढेर का उपयोग कैसे करते हैं। ध्यान दें कि मुझे लगता है कि आप तत्वों की संख्या नहीं जानते हैं, और यही कारण है कि हमें तब तक पॉप करना चाहिए जब तक कि हम न्यूनतम ढेर से कुछ भी बड़े या ढेर से कम न होने वाले न्यूनतम ढेर से कुछ पॉप न करें। ध्यान दें कि हम औसत लौटाते हैं क्योंकि {1, 2, 3, 4} जैसे सेट के मामले में औसत वास्तव में 2.5 (दो "मध्य" मानों का औसत) होता है। मैं मान प्रकार के रूप में double मान रहा हूं, लेकिन यह स्पष्ट रूप से कुछ भी हो सकता है। यहाँ:

double min = minheap.pop(); 
double max = maxheap.pop(); 
while(min < max) { 
    min = minheap.pop(); 
    max = maxheap.pop(); 
} 

return (min + max)/2; 

पॉपिंग के बाद से O(log n) है और हम O(n/2) मूल्यों पॉप करने के लिए है, इस O(n log n) है।

Answer 3

जावा में एक कामकाजी कार्यान्वयन, 2 ढेर, ओ (एन लॉग एन) का उपयोग कर। किसी भी समय मैं आकार में संतुलित दो ढेर रखता हूं (यानी वे 1 से अधिक भिन्न होते हैं, अगर हमने n% 2 == 1 जैसे तत्वों को दर्ज किया है)। औसत प्राप्त करना ओ (1) है। नया तत्व जोड़ना ओ (लॉग एन) है।

public class MedianOfStream { 

    private int count; 
    private PriorityQueue<Integer> highs, lows; 

    public MedianOfStream() { 
     highs = new PriorityQueue<Integer>(11, new Comparator<Integer>() { 
      @Override 
      public int compare(Integer arg0, Integer arg1) { 
       return arg0.compareTo(arg1); 
      } 
     }); 
     lows = new PriorityQueue<Integer>(11, new Comparator<Integer>() { 
      @Override 
      public int compare(Integer arg0, Integer arg1) { 
       return arg1.compareTo(arg0); 
      } 
     }); 
    } 

    private int getMedian() { 
     if (count == 0) 
      return 0; 
     if (lows.size() == highs.size()) { 
      return (lows.peek() + highs.peek())/2; 
     } else if (lows.size() < highs.size()) { 
      return highs.peek(); 
     } 
     return lows.peek(); 
    } 

    private void swap(){ 
     int h = highs.poll(); 
     int l = lows.poll(); 
     highs.add(l); 
     lows.add(h); 
    } 

    public int updateMedian(int n) { 
     count++; 

     if (count == 1) 
      lows.add(n); 

     else if (count==2) { 
      highs.add(n); 
      if(highs.peek()<lows.peek()) { 
       swap(); // O(log n) 
      } 
     } 

     else { 
      if (n > highs.peek()) { 
       lows.add(highs.poll()); // O(log n) 
       highs.add(n); // O(log n) 
      } else { 
       highs.add(lows.poll()); // O(log n) 
       lows.add(n); // O(log n) 
      } 
      if(highs.peek()<lows.peek()) { 
       swap(); // O(log n) 
      } 
     } 

     // if we added an even # of items, 
     // the heaps must be exactly the same size, 
     // otherwise we tolerate a 1-off difference 

     if (Math.abs(lows.size() - highs.size()) > (count % 2)) { 
      if (lows.size() < highs.size()) { 
       lows.add(highs.poll()); // O(log n) 
      } else { 
       highs.add(lows.poll()); // O(log n) 
      } 
     } 

     return getMedian(); // O(1) 
    } 
} 

Answer 4

जावास्क्रिप्ट समाधान दो ढेर का उपयोग कर:

function addNewNumber(minHeap, maxHeap, randomNumber) { 
    if (maxHeap.size() === minHeap.size()) { 
    if (minHeap.peek() && randomNumber > minHeap.peek()) { 
     maxHeap.insert(minHeap.remove()); 
     minHeap.insert(randomNumber); 
    } else { 
     maxHeap.insert(randomNumber); 
    } 
    } else { 
    if (randomNumber < maxHeap.peek()) { 
     minHeap.insert(maxHeap.remove()); 
     maxHeap.insert(randomNumber); 
    } else { 
     minHeap.insert(randomNumber); 
    } 
    } 
} 

function getMedian(minHeap, maxHeap) { 
    if (!maxHeap.size()) { 
    return 0; 
    } 
    if (minHeap.size() === maxHeap.size()) { 
    return (minHeap.peek() + maxHeap.peek())/2; 
    } else { 
    return maxHeap.peek(); 
    } 
}