एक सरणी में दशमलव प्रभावशाली संख्या

Question

हाल ही में मैं इस साक्षात्कार के प्रश्न पर आया:

आपको एक सरणी में वास्तविक संख्याएं दी गई हैं। सरणी में एक संख्या को दशमलव प्रभाव कहा जाता है यदि यह सरणी में n/10 बार से अधिक होता है। यह निर्धारित करने के लिए कि दिए गए सरणी में दशमलव प्रभावशाली है या नहीं (ओ) समय एल्गोरिदम दें।

अब मैं इस को हल करने के लिए कुछ तरीके हैं, और इस सवाल के किसी भी सामान्यीकरण के बारे में सोच सकते हैं

एक पास 1 में एक हैश तालिका बनाने के लिए हो सकता है (यानी किसी भी संख्या है कि एक सरणी में कश्मीर बार दिखाई देता है खोजने) , और फिर पास 2 में आवृत्तियां, जो हे (एन) होगा की संख्या की गणना, लेकिन साथ ही हे (एन) का उपयोग करता है अंतरिक्ष,

एक ही रास्ता using 9 buckets

नहीं है लेकिन, किसी भी तरह से है कि हम यह एक स्थिर जगह में कर सकता है ?? कोई सुझाव??

[संपादित करें] मैं 9 बाल्टी समाधान की जाँच नहीं की है, पाठकों नीचे

Answer 1

1. एनएम की टिप्पणी के माध्यम से जाना एक पाश और दुकान कर/वास्तविक संख्या की सरणी में मान जोड़ने के लिए पसंद कर सकते हैं [] int।

2. एक और लूप करें जो सरणी सूची मानों को 10 से विभाजित करता है यदि यह 1 से अधिक दशमलव है।

Answer 2

मैं बोयर-मूर बहुमत मतदान एल्गोरिथ्म here के आधार पर एक तरह से रेखांकित किया है।

आपको याद है (ऊपर) (m-1) तत्व जिन्हें हाल ही में दूसरों और संबंधित गणनाओं से अधिक बार देखा गया है। जब एक याद किया तत्व देखा जाता है, इसकी गणना बढ़ जाती है। जब कोई याद नहीं किया गया तत्व देखा जाता है, यदि कोई स्लॉट मुक्त होता है, तो आप इसे याद करते हैं और इसकी गणना 1 तक सेट करते हैं, अन्यथा आप याद किए गए तत्वों की सभी गणनाओं से 1 घटाते हैं। एक याद किया तत्व जिसका गिनती 0 पर जाती है भूल जाती है। 1/m से अधिक अनुपात वाले किसी भी तत्व को याद किए गए तत्वों में से एक है। यदि आपको प्राथमिकता नहीं पता है कि m-1n/m से अधिक होने वाले तत्व हैं, तो आपको याद किए गए तत्वों की घटनाओं की गणना करने के लिए एक दूसरा पास चाहिए।

संपादित करें: संकेतित पृष्ठ पर जाने के बाद, मुझे लगता है कि यह एक ही समाधान है, सिवाय इसके कि यह याद किए गए गैर-प्रभावशाली लोगों के लिए जिम्मेदार नहीं है।

एक बार यह समाप्त हो जाने के बाद 1 से अधिक की संख्या वाले किसी भी गणना चर के बाद सूची में 10 से अधिक उदाहरण हैं।

सही नहीं है, लेकिन सभी दशमलव प्रभावकों को अंत में >= 1 की गणना के साथ याद किया जाएगा। मैं वहां कोड के माध्यम से नहीं गया है, इसलिए इसमें त्रुटियां हो सकती हैं, लेकिन लापता जांच पास को छोड़कर, एल्गोरिदम सही है।

प्रस्तावित counterexample साथ सही ढंग से करता है, तो हम दूसरी पास है बांटा जाता है, राज्य अंत में विकसित

0 1 2 3 4 5 6 7 8 
1 1 1 1 1 1 1 1 1 // coming 9 
0 0 0 0 0 0 0 0 0 // all forgotten, no slots occupied, coming 10 
10 - - - - - - - - 
1 - - - - - - - - // coming 0 
10 0 - - - - - - - 
1 1 - - - - - - - 

, दो पर कब्जा कर लिया स्लॉट्स, 10 और 0 दोनों 1 की गणना के साथ याद किया जाता है देखते हैं।10 दशमलव प्रभावशाली नहीं है, लेकिन 0 है, और यह एकमात्र ऐसा है, जैसा कि दूसरे चेकिंग पास द्वारा सत्यापित किया जाएगा।

Answer 3

public static int[] KthDominants(int[] arr, int kth) 
    { 
     var data = new Dominants(arr.Length, kth); 
     for (int i = 0; i < arr.Length; i++) 
     { 
      data.Push(arr[i]); 
     } 
     return data.ToArray(); 
    } 

डोमिनेंट्स क्लास एक शब्दकोश में केथ -1 काउंटर स्टोर करता है। यह संग्रह के साथ काम करने के लिए System.Linq का उपयोग करता है।

public class Dominants 
{ 
    int _size; 
    int _kth; 
    int _grade; 
    Dictionary<int, int> _counters; 

    public Dominants(int size, int kth) 
    { 
     _size = size; 
     _kth = kth; 
     _counters = new Dictionary<int, int>(); 
    } 

    public void Push(int key) 
    { 
     if (_counters.ContainsKey(key)) 
      _counters[key]++; 
     else 
     { 
      // The trick is that the dominant element remains same 
      // if you delete any k distinct items from the array. 
      if (_counters.Count < _kth) 
       _counters.Add(key, 1); 
      else 
      { 
       foreach (var i in _counters.Keys.ToArray()) 
       { 
        if (_counters[i] > 1) 
         _counters[i]--; 
        else 
         _counters.Remove(i); 
       } 
       _grade++; 
      } 
     } 
    } 

    public int[] ToArray() 
    { 
     var cnt = _size/_kth - (_grade + 1); 
     return _counters 
      .Where(i => i.Value > cnt) 
      .Select(i => i.Key) 
      .ToArray(); 
    } 
} 

github

Answer 4

आप 3-वे-विभाजनजल्दी चयन (एन/10) वां सबसे बड़ा सरणी के तत्व को खोजने के लिए उपयोग कर सकते हैं, और फिर जाँच करें कि क्या यह दशमलव-प्रभावी है ; यदि नहीं, तो सही उप-सरणी में पुनरावृत्ति करें।

यह जगह में और रैखिक उम्मीद समय के भीतर किया जा सकता है, इसलिए सख्ती से स्थिर स्थान नहीं।