एरे

Question

में दोहराए गए सबएरे की संख्या पाएं 0-n (यानी आकार = एन) से 0-m से तत्वों को शामिल किया गया एक सरणी है जहां m < n (मान लीजिए मीटर 100 से 100 गुना कम है यानी मीटर से बहुत कम है) , तत्व या उप सरणी के इतने दोहराया जाना चाहिए और हम आकार 1 या 1. उदाहरण के लिए एक से अधिक के इस तरह के बार-बार उप सरणी की संख्या को खोजने के लिए है, एक सरणी
1 2 4 1 2 4 1 5 6 3 5, यहाँ
1 2 बार दोहराया है पर विचार
2 दो बार दोहराया गया है
4 दो बार दोहराया गया है
5 दोहराया है 1 समय
1 2 दोहराया है 1 समय
2 4 1 समय
4 1 दोहराया है दोहराया है 1 समय
1 2 4 दोहराया है 1 समय
2 4 1 दोहराया है 1 समय
1 2 4 1 1 समय
दोहराया है तो अंतिम जवाब इनमें से 11 या है, क्या कोई इसे हल करने के लिए कुछ डेटा संरचना या एक कुशल एल्गोरिदम सुझा सकता है। मैं हैशिंग एम के बारे में सोच रहा था और इंडेक्स वैल्यू को नोट कर रहा था जहां यह होता है लेकिन इसे औपचारिक रूप से लागू नहीं किया गया था।
मान लें n,m < 10^5

Answer 1

1. एक हैश बनाएं जिसमें पूर्णांक के रूप में पूर्णांक हैं, और मूल्यों के रूप में पूर्णांक की विस्तारित सूचियां (लिंक सूचियां, उदा।)।

2. अपनी इनपुट सूची के माध्यम से पढ़ें। एक कुंजी के रूप में स्कैन किए जाने वाले प्रत्येक इनपुट तत्व का इलाज करें; मानों की संबंधित सूची में निम्न तत्व की अनुक्रमणिका संलग्न करें।

3. अब, आपकी दोहराई गई 1-तत्व गणना एन - | कुंजी |

4. अगला, अपनी चाबियाँ से गुज़रें। प्रत्येक कुंजी के लिए, मूल सूची के अनुक्रमित तत्वों को एक नई इनपुट सूची के रूप में देखें। एक नया हैश बनाएं और चरण 1 में जारी रखें।ध्यान दें कि जब हम इंडेक्स स्टोर करते हैं तो हम मूल सूची के उन लोगों का उपयोग करना जारी रखते हैं।

उदाहरण: 1 2 4 1 2 4 1 5 6 3 5 (मान लें कि हम शून्य-अनुक्रमित हैं)। यहां, एन = 11।

• 1 -> [1, 4, 7]
• 2 -> [2, 5]
• 3 -> [10]
• 4 -> [3, 6]
• 5 -> [8, शून्य]
• 6 -> [9]

दोहराया 1-elts की संख्या 11 - 6 = 5.

अब, हम चाबियाँ के माध्यम से जाते हैं। हम 1 से शुरू करते हैं। सूचकांक सूची [1, 4, 7] है जो तत्वों [2, 2, 5] से मेल खाती है।

• 2 -> [2, 5]
• 5 -> [8]

यह 3 उठाता है - 2 = 1 डुप्लिकेट 2-तत्व सूची।

आदि ...

समय चल रहा है: इनपुट + उत्पादन

Answer 2

मैंने Skienna's book on the design of algorithms से प्रत्यय पेड़ों के आधार पर एक दृष्टिकोण का उपयोग किया। प्रत्यय के पेड़ एक विशेष प्रकार के trie tree हैं, जहां आप दिए गए स्ट्रिंग के प्रत्येक प्रत्यय को त्रिभुज पेड़ में डालते हैं। ट्री पेड़ एक ही पेड़ में एकाधिक शब्दों को संग्रहीत करने का एक तरीका है: रूट शून्य स्ट्रिंग है, और प्रत्येक किनारे एक चरित्र जोड़ती है। मैंने नीचे अवधारणा के सबूत के रूप में एक बहुत ही सरल कार्यान्वयन का उपयोग किया है।

#include <iostream> 
#include <string> 
using std::string; 
using std::cout; 

class Node 
{ 
    Node* m_descendants[10]; 
    int m_count; 
public: 
    Node() 
    { 
     for(int i=0; i<10; ++i) { m_descendants[i] = nullptr; } 
     m_count = 0; 
    } 
    void Add(const char* str) { 
     // Increment number of times we've reached this node 
     m_count++; 

     const int firstDigit = str[0] - '0'; 
     if (!(0 <= firstDigit && firstDigit <= 9)) return; // recursion base case 

     // Access descendant node correponding to current digit 
     Node*& descendant = m_descendants[firstDigit]; 
     if (descendant == 0) { // create descendant if necessary 
      descendant = new Node; 
     } 

     // Recurse on rest of string 
     descendant->Add(str +1); 
    } 
    void Print(const string& str, int countAdj=0) const // debug function 
    { 
     for(int nextDigit=0; nextDigit<10; ++nextDigit) { 
      const Node* node = m_descendants[nextDigit]; 
      if (node) { 
       const int adjustedCount = node->Count() - countAdj; 
       if (adjustedCount > 0) { 
        char c = '0' + nextDigit; 
        string strWithC = str; 
        strWithC += c; 
        cout << strWithC << ": " << adjustedCount << "\n"; 
        node->Print(strWithC, countAdj); 
       } 
      } 
     } 
    } 
    int SumRepeated() const 
    { 
     int sumRepeated = 0; 
     for(int nextDigit=0; nextDigit<10; ++nextDigit) { 
      const Node* node = m_descendants[nextDigit]; 
      if (node) { 
       const int repeatCount = node->Count() -1; 
       if (repeatCount > 0) { 
        sumRepeated += repeatCount; 
        sumRepeated += node->SumRepeated(); 
       } 
      } 
     } 
     return sumRepeated; 
    } 
    int Count() const { return m_count; } 
}; 

int main(int argc, const char* argv[]) 
{ 
    // Construct 
    Node* const root = new Node; 
    for(const char* str = "12412415635"; *str; ++str) { 
     root->Add(str); 
    } 

    // Print 
    root->Print(string(), 1); 

    cout << "Sum repeated is " << root->SumRepeated() << "\n"; 

    return 0; // (nodes are leaked) 
} 

आउटपुट

1: 2 
12: 1 
124: 1 
1241: 1 
2: 1 
24: 1 
241: 1 
4: 1 
41: 1 
5: 1 
Sum repeated is 11 

नोट वहाँ एक अतिरिक्त दोहराया सबस्ट्रिंग यहाँ, यानी 1241

जैसा कि मैंने कहा, इस अवधारणा का सबूत है, इसलिए, उदाहरण के लिए, आप चाहते हैं बड़े m के साथ, वंशजों को स्टोर करने के लिए सरणी के बजाय एक शब्दकोश का उपयोग करने के लिए। साथ ही, यह कार्यान्वयन समग्र एल्गोरिदम के संदर्भ में भी इष्टतम नहीं है: यह समय और स्थान में ओ (एन^2) है। ओ (एन) स्पेस प्राप्त करने के लिए आप किसी भी शाखा के बिना पथ को ध्वस्त करके ऑप्टिमाइज़ कर सकते हैं, और ओ (एन) समय प्राप्त करने के लिए चालाक निर्माण एल्गोरिदम का उपयोग कर सकते हैं। साथ ही, जैसा कि अन्य उत्तरों में से एक में बताया गया है, आपको उप-तारों को संसाधित करने की आवश्यकता नहीं है जो मूल की आधे लंबाई तक हैं।

Answer 3

यहाँ में रैखिक जावास्क्रिप्ट में कुछ है: (उत्पादन कम या ज्यादा तत्काल है और जावास्क्रिप्ट धीमी में से एक है, मुझे लगता है):

<script> 

function f (s, m) { 
    var i = 0, n = s.length, c = 0, H = {}, Hi = {} 
    while (i < n-1) { 
    for (var j=i+1; j<=Math.min (i + 1 + m,n - 1); j++) { 
     if (s[i] == s[j]) { 
     var i_= i, j_= j, tmp = '' 
     while (s[i_] == s[j_] && i_ < j) { 
      tmp += String (s[i_]) 
      i_++ 
      j_++ 
     } 
     var k = tmp.length - 1 
     while (k >= 0) { 
      if (!H[tmp]) { 
      H[tmp] = 1 
      Hi[tmp] = i 
      c++ 
      } 
      else if (i == Hi[tmp]) { 
      H[tmp]++ 
      c++ 
      } 
      tmp = tmp.substr(0,k--) 
     } 
     } 
    } 
    i++ 
    } 
    var t1 = '' 
    for (var i in H) t1 += i + ", " 
    return [t1,c] 
} 

var a1 = [1,2,4,1,2,4,1,5,6,3,5], 
    a2 = [] 

for (var i=0;i<100000;i++) a2.push(Math.floor(Math.random()*10)) 

console.log(a1 +"\n"+ f(a1,10)) 
console.log(f(a2,10)) 

</script> 

आउटपुट:

1,2,4,1,2,4,1,5,6,3,5 
1, 2, 4, 5, 12, 24, 41, 124, 241, ,10 

["0...6358, 3582, 038, 4304, 2068, 095, 
9252, 37866, 3786, 7866, 7893, 8701, 0669, ", 771]