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

C++ में दूसरे ऐरे के तत्वों को पुनर्व्यवस्थित करके बनने वाला लेक्सिकोग्राफिकली सबसे छोटा अनुक्रम खोजें


मान लीजिए हमारे पास n संख्याओं के दो ऐरे A और B हैं, हमें B के तत्वों को स्वयं में इस तरह पुनर्व्यवस्थित करना है कि पुनर्व्यवस्थित करने के बाद (A[i] + B[i]) % n से बना अनुक्रम लेक्सिकोग्राफिकली सबसे छोटा हो। अंत में हम लेक्सिकोग्राफिकली सबसे छोटा संभव अनुक्रम लौटाएंगे।

उदाहरण के लिए, यदि इनपुट A = {1, 2, 3, 2}, B = {4, 3, 2, 2} है, तो आउटपुट [0, 0, 1, 2] होगा।

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

  • n := a का आकार
  • my_map नामक एक मैप परिभाषित करें
  • my_set नामक एक सेट परिभाषित करें
  • i := 0 से n-1 तक लूप करें:
    • my_map[b[i]] बढ़ाएं
    • b[i] को my_set में डालें
  • सीक्वेंस नामक एक ऐरे परिभाषित करें
  • i := 0 से n-1 तक लूप करें:
    • यदि a[i] 0 के बराबर है:
      • it := my_set के तत्व जो 0 से छोटे नहीं हैं, शुरू में पहले तत्व पर इंगित करते हैं
      • वैल्यू := it
      • वैल्यू % n को सीक्वेंस के अंत में डालें
      • my_map[वैल्यू] घटाएं
      • यदि my_map[वैल्यू] शून्य है, तो my_set से वैल्यू हटाएं
    • अन्यथा:
      • x := n - a[i]
      • it := my_set के तत्व जो x से छोटे नहीं हैं, शुरू में पहले तत्व पर इंगित करते हैं
      • यदि it my_set में नहीं है, तो it := my_set के तत्व जो 0 से छोटे नहीं हैं
      • वैल्यू := it
      • (a[i] + वैल्यू) % n को सीक्वेंस के अंत में डालें
      • my_map[वैल्यू] घटाएं
      • यदि my_map[वैल्यू] शून्य है, तो my_set से वैल्यू हटाएं
  • सीक्वेंस लौटाएं

उदाहरण

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

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v) { cout << "["; for (int i = 0; i < v.size(); i++) { cout << v[i] << ", "; } cout << "]" << endl; } vector<int> solve(vector<int>&a, vector<int> &b) { int n = a.size(); unordered_map<int, int> my_map; set<int> my_set; for (int i = 0; i < n; i++) { my_map[b[i]]++; my_set.insert(b[i]); } vector<int> sequence; for (int i = 0; i < n; i++) { if (a[i] == 0) { auto it = my_set.lower_bound(0); int value = *it; sequence.push_back(value % n); my_map[value]--; if (!my_map[value]) my_set.erase(value); } else { int x = n - a[i]; auto it = my_set.lower_bound(x); if (it == my_set.end()) it = my_set.lower_bound(0); int value = *it; sequence.push_back((a[i] + value) % n); my_map[value]--; if (!my_map[value]) my_set.erase(value); } } return sequence; } int main() { vector<int> a = {1, 2, 3, 2}; vector<int> b = {4, 3, 2, 2}; vector<int> res = solve(a, b); print_vector(res); }

इनपुट

{1, 2, 3, 2}, {4, 3, 2, 2}

आउटपुट

[0, 0, 1, 2, ]

  1. - C++ प्रोग्राम: सरणी में सबसे छोटे मान की आवृत्ति ज्ञात करना

    यहां हम देखेंगे कि सरणी में सबसे छोटे तत्व की आवृत्ति कैसे ज्ञात करें। मान लें सरणी तत्व [5, 3, 6, 9, 3, 7, 5, 8, 3, 12, 3, 10] हैं, यहां सबसे छोटा तत्व 3 है, और इस तत्व की आवृत्ति 4 है। इसलिए आउटपुट 4 है। इसे हल करने के लिए हम सूची का सबसे छोटा तत्व ज्ञात करेंगे, फिर पहले नंबर की घटनाओं को गिनेंगे

  1. - C++ प्रोग्राम: वे तत्व ज्ञात करना जो पहली सरणी में हैं लेकिन दूसरी में नहीं

    मान लें हमारे पास दो सरणी A और B हैं। कुछ तत्व हैं। हमें वे तत्व ज्ञात करने हैं जो सेट A में मौजूद हैं, लेकिन सेट B में नहीं। यदि हम उस स्थिति के बारे में सोचते हैं, और A और B को सेट मानते हैं, तो यह मूल रूप से सेट विभाजन ऑपरेशन है। A और B के बीच सेट अंतर उन तत्वों को लौटाएगा। उदाहरण #include <i

  1. - C++ प्रोग्राम: सरणी के पार्टीशन विधि से kवां सबसे छोटा तत्व खोजें

    एल्गोरिदमCreatePartition() फ़ंक्शन बनाएं जिसमें सरणी a, निचली सीमा l और ऊपरी सीमा h हो। in := l और pi := h सेट करें। l से h तक लूप चलाएं, यदि a[i] < a[pi] तो a[i] और a[in] को स्वैप करें और in बढ़ाएं। अंत में a[pi] और a[in] को स्वैप करें और in लौटाएं। Partition() फ़ंक्शन में: यदि low k-1 तो Partitio