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

C++ में आकार K के प्रत्येक उप-सरणी में अधिकतम अद्वितीय तत्व

इस समस्या में, हमें पूर्णांकों की एक सरणी और एक पूर्णांक K दिया जाता है। हमारा कार्य एक ऐसा प्रोग्राम बनाना है जो बिना किसी डुप्लिकेट के आकार K के प्रत्येक उप-सरणी में अधिकतम अद्वितीय तत्व ढूंढेगा।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट -

array = {4, 1, 1, 3, 3}
k = 3

आउटपुट -

4 3 1

स्पष्टीकरण -

Sub-array of size 3
Subarray {4, 1, 1}, max = 4
Subarray {1, 1, 3}, max = 3
Subarray {1, 3, 3}, max = 1

इस समस्या को हल करने के लिए, एक आसान तरीका है दो लूप चलाना और सबएरे बनाना और अलग-अलग तत्वों को ढूंढना और उनमें से अधिकतम प्रिंट करना।

लेकिन एक प्रभावी समाधान स्लाइडिंग विंडो विधि . का उपयोग करना है अधिकतम तत्वों को खोजने के लिए हैश टेबल और सेल्फ-बैलेंसिंग BST का उपयोग करना।

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

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,

#include <bits/stdc++.h>
using namespace std;
void maxUniqueSubArrayElement(int A[], int N, int K){
   map<int, int> eleCount;
   for (int i = 0; i < K - 1; i++)
      eleCount[A[i]]++;
   set<int> uniqueMax;
   for (auto x : eleCount)
      if (x.second == 1)
         uniqueMax.insert(x.first);
   for (int i = K - 1; i < N; i++) {
      eleCount[A[i]]++;
      if (eleCount[A[i]] == 1)
          uniqueMax.insert(A[i]);
      else
         uniqueMax.erase(A[i]);
      if (uniqueMax.size() == 0)
         cout<<"-1\t" ;
      else
         cout<<*uniqueMax.rbegin()<<"\t";
      int x = A[i - K + 1];
      eleCount[x]--;
      if (eleCount[x] == 1)
         uniqueMax.insert(x);
      if (eleCount[x] == 0)
         uniqueMax.erase(x);
   }
}
int main(){
   int a[] = { 4, 3, 2, 2, 3, 5};
   int n = sizeof(a) / sizeof(a[0]);
   int k = 4;
   cout<<"The maximum unique element for a subarray of size "<<k<<" is\n";
      maxUniqueSubArrayElement(a, n, k);
   return 0;
}

आउटपुट

The maximum unique element for a subarray of size 4 is 4 -1 5

  1. C++ में उपसर्ग योग का उपयोग करते हुए O(n) में अधिकतम सबअरे योग

    समस्या कथन सकारात्मक और नकारात्मक पूर्णांकों की एक सरणी को देखते हुए, उस सरणी में अधिकतम सबअरे योग ज्ञात करें उदाहरण यदि इनपुट ऐरे − {-12, -5, 4, -1, -7, 1, 8, -3} है तो आउटपुट 9 है एल्गोरिदम इनपुट सरणी के उपसर्ग योग की गणना करें। प्रारंभ करें− min_prefix_sum =0, रेस =-अनंत i =0 से n के ल

  1. कम से कम X के आकार के उप-सरणी का अधिकतम औसत और C++ में अधिकतम Y

    समस्या कथन एक सरणी गिरफ्तारी [] और दो पूर्णांक X और Y को देखते हुए। कार्य कम से कम X के आकार की एक उप-सरणी और अधिकतम औसत के साथ अधिकतम Y को खोजना है उदाहरण यदि इनपुट ऐरे {2, 10, 15, 7, 8, 4} और x =3 और Y =3 है तो हम निम्न प्रकार से अधिकतम औसत 12.5 प्राप्त कर सकते हैं - (10 + 15) / 2 = 12.5 एल्गोरि

  1. सी ++ में न्यूनतम ढेर में अधिकतम तत्व

    समस्या कथन न्यूनतम ढेर को देखते हुए उसमें अधिकतम तत्व खोजें। उदाहरण यदि इनपुट हीप है - तब अधिकतम तत्व 55 . है एल्गोरिदम न्यूनतम हीप में पैरेंट नोड अपने बच्चों से छोटा होगा। इसलिए हम यह निष्कर्ष निकाल सकते हैं कि एक गैर-पत्ती नोड अधिकतम नहीं हो सकता। लीफ नोड्स में अधिकतम तत्व खोजें उदाहरण आइए