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

C++ में डुप्लीकेट सरणी से खोए हुए तत्व का पता लगाएं

अवधारणा

दिए गए दो सरणियों के संबंध में जो एक तत्व को छोड़कर एक दूसरे के डुप्लिकेट हैं, इसका मतलब है कि सरणी में से एक तत्व गायब है, उस लापता तत्व को निर्धारित करना हमारा कार्य है।

इनपुट

arr1[] = {2, 5, 6, 8, 10}
arr2[] = {5, 6, 8, 10}

आउटपुट

2

2 दूसरी सरणी से गायब है।

इनपुट

arr1[] = {3, 4, 5, 6}
arr2[] = {3, 4, 5, 6, 7}

आउटपुट

7

7 पहली सरणी से गायब है।

विधि

यहां, हम एक सरल समाधान लागू करते हैं जहां हम सरणियों पर पुनरावृति करते हैं और तत्व द्वारा तत्व को सत्यापित करते हैं और एक बेजोड़ का पता चलने पर लापता तत्व को चिह्नित करते हैं। लेकिन इस समाधान का दोष यह है कि इसे सरणी के आकार से अधिक रैखिक समय की आवश्यकता होती है।

हम एक और कुशल समाधान लागू कर सकते हैं जो द्विआधारी खोज दृष्टिकोण पर आधारित है। हम नीचे दिए गए एल्गोरिदम का पालन करते हैं जिसे चरण दर चरण समझाया गया है -

  • बाइनरी सर्च को बड़े एरे में शुरू करें और बीच में (निम्न + उच्च) / 2 प्राप्त करें
  • यह देखा गया है कि यदि दोनों सरणी से मान समान है तो लापता तत्व दाएं भाग में होना चाहिए इसलिए मध्य के रूप में कम चिह्नित करें
  • अन्यथा मध्य के रूप में उच्च चिह्नित करें क्योंकि लापता तत्व बड़े सरणी के बाएं हिस्से में होना चाहिए यदि मध्य तत्व समान नहीं हैं।
  • हमें विशेष मामले को अलग से संभालना होगा क्योंकि एकल तत्व और शून्य तत्व सरणी के लिए, एकल तत्व ही लापता तत्व होगा।

यह देखा गया है कि यदि पहला तत्व स्वयं समान नहीं है तो वह तत्व लुप्त तत्व होगा।

उदाहरण

// C++ program to find missing element from same
// arrays (except one missing element)
#include <bits/stdc++.h>
using namespace std;
// Shows function to determine missing element based on binary
// search approach. arrA[] is of larger size and
// Q is size of it. arrA[] and arrB[] are assumed
// to be in same order.
int findMissingUtil(int arrA[], int arrB[], int Q){
   // Considers special case, for only element which is
   // missing in second array
   if (Q == 1)
      return arrA[0];
   // Considers special case, for first element missing
   if (arrA[0] != arrB[0])
      return arrA[0];
   // Used to initialize current corner points
   int low = 0, high = Q - 1;
   // Iterate until low < high
   while (low < high){
      int mid = (low + high) / 2;
      // It has been observed that if element at mid indices are equal
      // then go to right subarray
      if (arrA[mid] == arrB[mid])
         low = mid;
      else
         high = mid;
         // So if low, high becomes contiguous, break
      if (low == high - 1)
      break;
   }
   // Now missing element will be at high index of
   // bigger array
   return arrA[high];
}
// So this function mainly does basic error checking
// and calls findMissingUtil
void findMissing(int arrA[], int arrB[], int P, int Q){
   if (Q == P-1)
      cout << "Missing Element is "
      << findMissingUtil(arrA, arrB, P) << endl;
   else if (P == Q-1)
      cout << "Missing Element is "
      << findMissingUtil(arrB, arrA, Q) << endl;
   else
   cout << "Invalid Input";
}
// Driver Code
int main(){
   int arrA[] = {2, 5, 6, 8, 10};
   int arrB[] = {5, 6, 8, 10};
   int P = sizeof(arrA) / sizeof(int);
   int Q = sizeof(arrB) / sizeof(int);
   findMissing(arrA, arrB, P, Q);
   return 0;
}

आउटपुट

Missing Element is 2

  1. सी ++ में सरणी में प्रत्येक तत्व की सर्पासर गणना खोजें

    मान लीजिए कि एक सरणी A दिया गया है। हमें उस सरणी में प्रत्येक तत्व की संख्या को पार करना होगा। पार करने वाले अधिक से अधिक तत्व होते हैं जो वर्तमान तत्व की सरणी के दाईं ओर मौजूद होते हैं। मान लीजिए A ={2, 7, 5, 3, 0, 8, 1}, श्रेष्ठ हैं {4, 1, 1, 2, 0, 0}, तो 2 में दायीं ओर 4 संख्याएँ हैं, जो बड़ी हैं

  1. सी ++ प्रोग्राम एक ऐरे का सबसे बड़ा तत्व खोजने के लिए

    एक सरणी में कई तत्व होते हैं और एक सरणी में सबसे बड़ा तत्व वह होता है जो अन्य तत्वों से बड़ा होता है। उदाहरण के लिए। 5 1 7 2 4 उपरोक्त सरणी में, 7 सबसे बड़ा तत्व है और यह इंडेक्स 2 पर है। किसी सरणी के सबसे बड़े तत्व को खोजने का प्रोग्राम इस प्रकार दिया गया है। उदाहरण #include <iostream> u

  1. पायथन में एक डुप्लीकेट सरणी से खोए हुए तत्व का पता लगाएं

    मान लीजिए कि हमारे पास दो सरणियाँ हैं जो एक तत्व को छोड़कर एक दूसरे के डुप्लिकेट हैं, इसलिए, दिए गए सरणी में से एक तत्व गायब है, हमें उस लापता तत्व को ढूंढना होगा। इसलिए, यदि इनपुट ए =[2, 5, 6, 8, 10], बी =[5, 6, 8, 10] जैसा है, तो आउटपुट 2 होगा क्योंकि दूसरी सरणी से 2 गायब है। इसे हल करने के लिए,