लगाएं कि ऐसा एक तत्व खुद को दोहरा n/कश्मीर बार

Question

आप एक सरणी आकार n और है एक निरंतरk (जो)

आप मान सकते हैं सरणी (पूर्णांक प्रकार का है, हालांकि यह की हो सकता है किसी भी प्रकार)

एक एल्गोरिदम का वर्णन करें जो पाता है कि कोई तत्व है जो कम से कम n/k बार दोहराता है ... यदि कोई वापसी हो। रैखिक समय में ऐसा (O(n))

पकड़: इस एल्गोरिथ्म करते हैं (या यहां तक ​​कि छद्म कोड) निरंतर स्मृति का उपयोग और केवल दो बार

Answer 1

1. तत्वों और उनकी गणनाओं को संग्रहित करने के लिए आकार (के -1) का एक अस्थायी सरणी बनाएं (आउटपुट तत्व इन के -1 तत्वों में से एक होने जा रहे हैं)।

2. इनपुट सरणी और के माध्यम से पार अद्यतन अस्थायी [] (जोड़ें/एक तत्व या वृद्धि/कमी गिनती निकालने के लिए) हर चल तत्व के लिए। सरणी temp [] हर कदम पर संभावित (के -1) उम्मीदवारों को स्टोर करता है। यह कदम ओ (एनके) समय लेता है।

3. अंतिम (K-1) संभावित उम्मीदवारों के माध्यम से दोहराएं (अस्थायी में [] संग्रहीत)। या प्रत्येक तत्व, जांचें कि वास्तव में यह एन/के से अधिक गिनती है या नहीं। यह कदम ओ (एनके) समय लेता है।

मुख्य चरण चरण 2 है, हर बिंदु पर संभावित उम्मीदवारों को कैसे बनाए रखा जाए? चरण 2 में उपयोग किए गए कदम मशहूर गेम की तरह हैं: टेट्रिस। हम टेट्रिस में एक टुकड़े के रूप में प्रत्येक नंबर का इलाज करते हैं, जो हमारे अस्थायी सरणी temp [] में गिर जाता है। हमारा कार्य एक ही कॉलम पर एक ही संख्या को रखने की कोशिश करना है (अस्थायी सरणी में गिनती बढ़ी है)।

Consider k = 4, n = 9 
Given array: 3 1 2 2 2 1 4 3 3 

i = 0 
     3 _ _ 
temp[] has one element, 3 with count 1 

i = 1 
     3 1 _ 
temp[] has two elements, 3 and 1 with 
counts 1 and 1 respectively 

i = 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 1, 1 and 1 respectively. 

i = 3 
     - - 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 1, 1 and 2 respectively. 

i = 4 
     - - 2 
     - - 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 1, 1 and 3 respectively. 

i = 5 
     - - 2 
     - 1 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 1, 2 and 3 respectively. 
Now the question arises, what to do when temp[] is full and we see a new element – we remove the bottom row from stacks of elements, i.e., we decrease count of every element by 1 in temp[]. We ignore the current element. 

i = 6 
     - - 2 
     - 1 2 
temp[] has two elements, 1 and 2 with 
counts as 1 and 2 respectively. 

i = 7 
      - 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 1, 1 and 2 respectively. 

i = 8   
     3 - 2 
     3 1 2 
temp[] has three elements, 3, 1 and 2 with 
counts as 2, 1 and 2 respectively. 

अंत में, हमारे पास temp [] में अधिकांश के -1 नंबर हैं। अस्थायी तत्व {3, 1, 2} हैं। ध्यान दें कि temp [] में गणना अब बेकार हैं, गणना केवल चरण 2 में आवश्यक थी। अब हमें यह जांचने की आवश्यकता है कि temp [] में तत्वों की वास्तविक गणना n/k (9/4) से अधिक है या नहीं। तत्व 3 और 2 की संख्या 9/4 से अधिक है। तो हम प्रिंट 3 और 2

ध्यान दें कि एल्गोरिथ्म किसी भी उत्पादन तत्व याद नहीं करता है। दो संभावनाएं हो सकती हैं, कई घटनाएं एक साथ हैं या सरणी में फैली हुई हैं। यदि घटनाएं एक साथ हैं, तो गिनती अधिक होगी और 0 नहीं बन जाएगी। अगर घटनाएं फैलती हैं, तो तत्व अस्थायी रूप से फिर से आ जाएगा []। उपरोक्त एल्गोरिदम के सी ++ कार्यान्वयन के बाद निम्नलिखित है।

// A C++ program to print elements with count more than n/k 
#include<iostream> 
using namespace std; 

// A structure to store an element and its current count 
struct eleCount 
{ 
    int e; // Element 
    int c; // Count 
}; 

// Prints elements with more than n/k occurrences in arr[] of 
// size n. If there are no such elements, then it prints nothing. 
void moreThanNdK(int arr[], int n, int k) 
{ 
    // k must be greater than 1 to get some output 
    if (k < 2) 
     return; 

    /* Step 1: Create a temporary array (contains element 
     and count) of size k-1. Initialize count of all 
     elements as 0 */ 
    struct eleCount temp[k-1]; 
    for (int i=0; i<k-1; i++) 
     temp[i].c = 0; 

    /* Step 2: Process all elements of input array */ 
    for (int i = 0; i < n; i++) 
    { 
     int j; 

     /* If arr[i] is already present in 
      the element count array, then increment its count */ 
     for (j=0; j<k-1; j++) 
     { 
      if (temp[j].e == arr[i]) 
      { 
       temp[j].c += 1; 
       break; 
      } 
     } 

     /* If arr[i] is not present in temp[] */ 
     if (j == k-1) 
     { 
      int l; 

      /* If there is position available in temp[], then place 
       arr[i] in the first available position and set count as 1*/ 
      for (l=0; l<k-1; l++) 
      { 
       if (temp[l].c == 0) 
       { 
        temp[l].e = arr[i]; 
        temp[l].c = 1; 
        break; 
       } 
      } 

      /* If all the position in the temp[] are filled, then 
       decrease count of every element by 1 */ 
      if (l == k-1) 
       for (l=0; l<k; l++) 
        temp[l].c -= 1; 
     } 
    } 

    /*Step 3: Check actual counts of potential candidates in temp[]*/ 
    for (int i=0; i<k-1; i++) 
    { 
     // Calculate actual count of elements 
     int ac = 0; // actual count 
     for (int j=0; j<n; j++) 
      if (arr[j] == temp[i].e) 
       ac++; 

     // If actual count is more than n/k, then print it 
     if (ac > n/k) 
      cout << "Number:" << temp[i].e 
       << " Count:" << ac << endl; 
    } 
} 

/* Driver program to test above function */ 
int main() 
{ 
    cout << "First Test\n"; 
    int arr1[] = {4, 5, 6, 7, 8, 4, 4}; 
    int size = sizeof(arr1)/sizeof(arr1[0]); 
    int k = 3; 
    moreThanNdK(arr1, size, k); 

    cout << "\nSecond Test\n"; 
    int arr2[] = {4, 2, 2, 7}; 
    size = sizeof(arr2)/sizeof(arr2[0]); 
    k = 3; 
    moreThanNdK(arr2, size, k); 

    cout << "\nThird Test\n"; 
    int arr3[] = {2, 7, 2}; 
    size = sizeof(arr3)/sizeof(arr3[0]); 
    k = 2; 
    moreThanNdK(arr3, size, k); 

    cout << "\nFourth Test\n"; 
    int arr4[] = {2, 3, 3, 2}; 
    size = sizeof(arr4)/sizeof(arr4[0]); 
    k = 3; 
    moreThanNdK(arr4, size, k); 

    return 0; 
} 

Answer 2

सरणी पर चल रहा 100% यकीन नहीं है, लेकिन यह लग रहा है जैसे आप the Britney Spears problem — को हल करना चाहते हैं जो एक आइटम ढूंढ रहा है जो स्थिर स्मृति का उपयोग करके नमूना का एक निश्चित अंश बनाता है।

यहाँ समाधान का चित्र के साथ, अंग्रेजी में समस्या का एक कथन है:

है & hellip; एरिक डी 2002 के एमआईटी और अलेजैंड्रो लॉपेज़-ऑर्टिज़ और जे। इयान मुनरो कनाडा में वाटरलू विश्वविद्यालय। Demaine और उनके सहयोगियों ने एल्गोरिथ्म विस्तार किया है एक अधिक-सामान्य समस्या को कवर करने के:, n लंबाई की एक धारा देखते हुए कि सभी तत्व शामिल हैं आकार मीटर का एक सेट एक आवृत्ति के साथ होने वाली पहचान अधिक से अधिक से n/(एम +1)। (एम = 1, के मामले में यह बहुमत की समस्या को कम कर देता है।) विस्तारित एल्गोरिदम के लिए उम्मीदवार तत्व के साथ-साथ एम काउंटर के लिए एम रजिस्टरों की आवश्यकता होती है। मूल संचालन की योजना बहुमत वाले एल्गोरिदम के के समान है। जब स्ट्रीम तत्व उम्मीदवारों में से एक से मेल खाता है, तो संबंधित काउंटर बढ़ता है; जब किसी भी उम्मीदवार को कोई मिलान नहीं होता है, तो सभी काउंटर कम हो जाते हैं; यदि काउंटर 0 पर है, संबंधित उम्मीदवार को स्ट्रीम से नए तत्व द्वारा को प्रतिस्थापित किया गया है।

Answer 3

एक साधारण ओ (एन) एल्गोरिदम पाया गया उदाहरणों की संख्या से मिले नंबर से एक हैश नक्शा रखना होगा। ओ (एन) को बनाए रखने के लिए एक हैश नक्शा का उपयोग करना महत्वपूर्ण है। , नक्शे पर एक अंतिम पास जवाब प्रकट करेगा। यह पास ओ (एन) भी है क्योंकि सबसे खराब स्थिति परिदृश्य यह है कि प्रत्येक तत्व केवल एक बार दिखाई देता है और इसलिए नक्शा मूल सरणी के समान आकार होता है।

Answer 4

मुझे नहीं पता कि आप प्रतिबंधित हैं कि आप किस अतिरिक्त डेटा संरचनाओं का उपयोग कर सकते हैं।

'तत्व' < -> मैपिंग गिनती के साथ हैशमैप बनाने के बारे में क्या। सम्मिलन ओ (लॉग एन) है। लुकअप ओ (1) है। प्रत्येक तत्व के लिए, हैशटेबल पर लुकअप करें, अगर गिनती 1 के साथ मौजूद नहीं है तो सम्मिलित करें। यदि मौजूद है, तो < (एन/के) गिनती है या नहीं। यह ओ (एन) रहेगा।

संपादित करें:

मैं लगातार स्मृति प्रतिबंध भूल गया। यह एन तत्वों के साथ हैश नक्शा प्रविष्टियों preallocating है?

Answer 5

दो आम (सैद्धांतिक) हे में इस समस्या का दृष्टिकोण (एन)

मैं) पहला विचार सरल

चरण 1 है) से अधिक अलग-अलग एलीमेंट k हैं, कश्मीर का चयन कर रहे हैं अलग तत्व और उन्हें मिटा दें। - 1 बार ध्यान दें कि कदम सबसे n/कश्मीर पर निष्पादित किया जाएगा जबकि: इसके लिए

चरण 2) टेस्ट सब कश्मीर अलग शेष तत्व आवृत्ति शुद्धता के

सबूत है। मान लीजिए कि ऐसा कोई तत्व है जो कम से कम n/k बार दोहराता है। सबसे बुरे मामले में इसे सभी एन/के -1 पुनरावृत्तियों में चुना जा सकता है और यह परीक्षण के बाद भी अंतिम सरणी में होगा, यह पाया जाएगा।

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

जटिलता: इस मानचित्र के सबसे खराब दृष्टिकोण को ध्यान में रखते हुए, ओ (एन * के) = ओ (एन), के रूप में के contant है।

चरण 2 सब (अधिकतम) की आवृत्ति कश्मीर -1 तत्वों जटिलता की गणना के द्वारा लागू किया जा सकता: हे (k * एन) = हे (एन)

कुल मिलाकर जटिलता: हे (एन) + O (एन) = ओ (एन)। (कार्यान्वयन से अलग एक छोटा सा विवरण है, 1 तत्व का अंतर, ऐसा इसलिए होता है क्योंकि हम स्यूडोकोड में बिल्कुल एन/के दोहराव के आवृत्ति के मामले को कवर करना चाहते हैं, यदि नहीं, तो हम एक और पुनरावृत्ति की अनुमति दे सकते हैं संभवतः के के अलग-अलग तत्व हैं, के लिए आवश्यक नहीं हैं)

II) दूसरा एल्गोरिदम रैखिक समय http://en.wikipedia.org/wiki/Selection_algorithm में चयन एल्गोरिदम का उपयोग करता है और विभाजन एल्गोरिदम जो रैखिक समय में भी चलता है। उनका उपयोग करके, आप अपने सरणी को के -1 बाल्टी में विभाजित करते हैं, इनवेरिएंट के साथ कि ith बाल्टी में कोई भी तत्व जे के बाल्टी में किसी भी तत्व से छोटा या बराबर होता है I> n (n) में। लेकिन ध्यान दें कि प्रत्येक बाल्टी के अंदर तत्वों को क्रमबद्ध नहीं किया जाता है।

अब, आप इस तथ्य का उपयोग करते हैं कि प्रत्येक बाल्टी में n/(k-1) तत्व होते हैं, और आप एक तत्व की तलाश में हैं जो कम से कम (n/k), और (n/k)> n को दोहराता है/(2 * (k-1))। यह बहुसंख्यक प्रमेय का उपयोग करने के लिए पर्याप्त है, जो बताता है कि यदि कोई तत्व बहुमत है (2 से विभाजित तत्वों की संख्या से अधिक बार), तो यह सरणी का औसत भी है। आप चयन एल्गोरिदम का उपयोग करके फिर से औसत प्राप्त कर सकते हैं।

तो, आप केवल विभाजन के लिए सभी मध्यस्थों और सभी पिवटों का परीक्षण करते हैं, जिन्हें आपको परीक्षण करने की आवश्यकता होती है क्योंकि वे दो अलग-अलग बाल्टी में बराबर मान विभाजित कर सकते हैं, के -1 + के मूल्य, जटिलता ओ ((2 * के -1) * एन)) = ओ (एन)।

Answer 6

यह झटकेदार एल्गोरिथ्म के अपने कार्यान्वयन ऊपर वर्णित है:

#include <map> 
#include <vector> 
#include <iostream> 
#include <algorithm> 

std::vector<int> repeatingElements(const std::vector<int>& a, int k) 
{ 
    if (a.empty()) 
     return std::vector<int>(); 

    std::map<int, int> candidateMap; //value, count; 

    for (int i = 0; i < a.size(); i++) 
    { 
     if (candidateMap.find(a[i]) != candidateMap.end()) 
     { 
      candidateMap[a[i]]++; 
     } 
     else 
     { 
      if (candidateMap.size() < k-1) 
      { 
       candidateMap[a[i]] = 1; 
      } 
      else 
      { 
       for (std::map<int, int>::iterator iter = candidateMap.begin(); 
        iter != candidateMap.end();) 
       { 
        (iter->second)--; 

        if (iter->second == 0) 
        { 
         iter = candidateMap.erase(iter); 
        } 
        else 
        { 
         iter++; 
        } 
       } 
      } 
     } 
    } 

    std::vector<int> ret; 

    for (std::map<int, int>::iterator iter = candidateMap.begin(); 
     iter != candidateMap.end(); iter++) 
    { 
     int candidate = iter->first; 

     if (std::count(a.begin(), a.end(), candidate) > (a.size()/k)) 
     { 
      ret.push_back(candidate); 
     } 
    } 

    return ret; 
} 

int main() 
{ 
    std::vector<int> a = { 1, 1, 4, 2, 2, 3, 3 }; 
    int k = 4; 

    std::vector<int> repeating_elements = repeatingElements(a, k); 

    for (int elem : repeating_elements) 
    { 
     std::cout << "Repeating more than n/" << k << " : " << elem << std::endl; 
    } 

    return 0; 
} 

और उत्पादन होता है:

n/4 की तुलना में अधिक दोहरा: 1

एन से ज्यादा दोहरा/4: 2

दोहरा और अधिक से अधिक n/4: 3