Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ कोड: हैश कॉलिजन होने वाले इंडेक्स का पता लगाना


मान लीजिए हमारे पास एक संख्या p और n तत्वों वाली एक और सरणी X है। p बकेट्स के साथ एक हैश टेबल है। बकेट्स 0 से p-1 तक नंबर दिए गए हैं। हम X से n संख्याएं डालना चाहते हैं। हम X[i] के लिए मान रहे हैं, इसका बकेट हैश फ़ंक्शन h(X[i]) द्वारा चुना जाएगा, जहां h(k) = k mod p। एक बकेट एक से अधिक तत्व नहीं रख सकता। यदि हम किसी संख्या को उस बकेट में डालना चाहते हैं जो पहले से भरा हुआ है, तो हम कहते हैं कि एक "कॉलिजन" होता है। हमें वह इंडेक्स लौटाना है जहां कॉलिजन हुआ है। यदि कोई कॉलिजन नहीं है, तो -1 लौटाएं।

इसलिए, यदि इनपुट p = 10; X = [0, 21, 53, 41, 53] है, तो आउटपुट 3 होगा, क्योंकि पहला 0 में डाला जाएगा, दूसरा 1 में, तीसरा 3 में, लेकिन चौथा 1 में डालने का प्रयास करेगा लेकिन वहां कॉलिजन है, इंडेक्स यहां 3 है।

चरण

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

n := size of X Define an array arr of size: p and fill with 0 for initialize i := 0, when i < n, update (increase i by 1), do:    x := X[i]    if arr[x mod p] is non-zero, then:       return i    increase arr[x mod p] by 1 return -1

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; int solve(int p, vector<int> X){    int n = X.size();    int arr[p] = { 0 };    for (int i = 0; i < n; i++){       int x = X[i];       if (arr[x % p]){          return i;       }       arr[x % p]++;    }    return -1; } int main(){    int p = 10;    vector<int> X = { 0, 21, 53, 41, 53 };    cout << solve(p, X) << endl; }

इनपुट

10, { 0, 21, 53, 41, 53 }

आउटपुट

3

  1. - C++ कोड: न्यूनतम अंकगणितीय माध्य विचलन ढूंढें

    मान लीजिए हमारे पास 3 तत्वों वाला एक सरणी A है। A[1], A[0] और A[2] का अंकगणितीय माध्य है यदि A[0] + A[2] = 2 * A[1]। तीन संख्याओं का अंकगणितीय माध्य विचलन d(A[0], A[1], A[2]) = |A[0] + A[2] - 2*A[1]| है। हम निम्नलिखित संक्रियाएं कितनी भी बार कर सकते हैं: सूचकांक {0, 1, 2} से दो सूचकांक i और j चुनें

  1. - C++ कोड: बैटरी संयोजनों की संख्या ढूंढें

    मान लीजिए, हमारे पास n बैटरी हैं जिनका अधिकतम 5 बार उपयोग किया जा सकता है। हमारे पास कुछ उपकरण हैं जिन्हें तीन बैटरी की आवश्यकता होती है और उपकरण का प्रत्येक उपयोग बैटरी के उपयोग काउंट को 1 से बढ़ाता है। यदि हमें उपकरणों का k बार उपयोग करना है, तो हमें यह पता लगाना है कि उपकरणों को पावर देने के लिए

  1. - C++ प्रोग्राम: स्ट्रिंग में वर्ण का अंतिम सूचकांक ज्ञात करना

    मान लें हमारे पास एक स्ट्रिंग str है। हमारे पास एक अन्य वर्ण ch है। हमारा कार्य स्ट्रिंग में ch का अंतिम सूचकांक ज्ञात करना है। मान लें स्ट्रिंग Hello है, और वर्ण ch = l, तो अंतिम सूचकांक 3 होगा। इसे हल करने के लिए, हम सूची को दाएं से बाएं पार करेंगे, यदि वर्ण l के समान नहीं है, तो सूचकांक घटाएं, य