एक और एरे का उपयोग करके तत्वों को अधिकतम करें


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना कट्टरपंथियों चौपाई
ऐरे हैश छंटाई

मान लीजिए, हमने एक ही आकार के दो पूर्णांक सरणी दिए हैं n। दोनों सरणियों में सकारात्मक संख्याएं हैं। समस्या कथन दूसरे सरणी तत्व को प्राथमिकता के रूप में रखते हुए दूसरे सरणी तत्व का उपयोग करके पहले सरणी को अधिकतम करने के लिए कहता है (दूसरे सरणी के तत्व पहले आउटपुट में दिखाई देने चाहिए)। जो सरणी बनाई गई है उसमें समाहित होना चाहिए n दोनों सरणियों के अद्वितीय लेकिन सबसे बड़े तत्व।

उदाहरण

arr1[] = {3,7,9,1,4}
arr2[] = {2,8,6,5,3}
{8, 6, 5, 7, 9}
arr1[] = {9,3,2}
arr2[] = {6,4,1}
{6, 4, 9}

कलन विधि

  1. एक बनाएं सरणी 2 * n का आकार।
  2. पहले दूसरे एरे तत्वों को एक निर्मित एरे में स्टोर करें और फिर पहले एरे तत्वों को।
  3. गैर-आरोही क्रम में सरणी को क्रमबद्ध करें।
  4. सरणी के n मानों को इसमें संग्रहीत करें सेट.
  5. उन्हें क्रम में व्यवस्थित करें क्योंकि वे पहले array2 को लेकर इनपुट के रूप में आते हैं और जाँचते हैं कि क्या इसका तत्व सेट में मौजूद है और उन्हें 0 से तीसरे सरणी में संग्रहीत करेंth सूचकांक.
  6. पहले सरणी के लिए उपरोक्त प्रक्रिया दोहराएं।
  7. परिणामी सरणी प्रिंट करें।

व्याख्या

हमारे पास दो हैं पूर्णांकों सरणी। हमें पहले सरणी को इस तरह से अधिकतम करने की आवश्यकता है कि जिस सरणी का गठन किया गया है उसमें दूसरा सरणी तत्व पहले और फिर पहला सरणी हो। इसमें सम्‍मिलित होना चाहिए n दोनों सरणियों से अद्वितीय और महान तत्व। आदेश को बनाए रखा जाना चाहिए, यदि तत्व पहले आता है तो इसे दूसरे सरणी में भी पहले आना चाहिए। इसे हल करने के लिए 2 * n आकार की एक सरणी बनाएं क्योंकि हमारे पास आकार n के रूप में दी गई एक सरणी है और हमें बस दोनों सरणियों के तत्वों को संग्रहीत करने की आवश्यकता है।

दूसरे सरणी के तत्वों को पहले हमारे द्वारा बनाए गए सरणी में संग्रहीत करें और फिर पहले सरणी के तत्वों को बनाए गए सरणी में संग्रहीत करें। हम ऐसा कर रहे हैं क्योंकि हम सेट किए गए सरणी के सभी मानों को सेट करने जा रहे हैं। क्योंकि इस कोड को हल करने के लिए हम एक सेट का उपयोग करने जा रहे हैं। सेट में निर्मित सरणी के सभी मूल्यों को सम्मिलित करने के बाद। हम गैर-आरोही क्रम में सरणी को सॉर्ट करेंगे।

हम सरणी से n समय तक मान सम्मिलित करने के लिए सेट में एक जगह बनाएंगे। एन बार के लिए है, हमारे पास पहले से ही गैर-आरोही क्रम में सॉर्ट किया गया सरणी है, हमें अभी इस पर कुछ संचालन करने के लिए पहले एन तत्वों की आवश्यकता है। सेट के सम्मिलन के बाद, हमारे पास सेट में सबसे बड़ा n मान है। अब हमें उनके ऑर्डर के अनुसार उस वैल्यू को व्यवस्थित करने की आवश्यकता है क्योंकि वे इनपुट में आते हैं, इसलिए हम एरे को दूसरी तरह से आगे बढ़ाएंगे क्योंकि वह एरे हमारी प्राथमिकता है। इसलिए अगर हमें किसी सेट में मौजूद एरे के तत्वों में से कोई भी मिला। हम 0 वें स्थान से बनाई गई सरणी को अपडेट करेंगे और पहले सरणी के लिए भी जाँच करेंगे और सरणी तीसरे में इसके मूल्यों को अपडेट करेंगे।

अब array3 के मानों को array1 में अपडेट करें और array1 को प्रिंट करें, और इसी तरह हम पहली सरणी को अधिकतम करते हैं, दूसरे सरणी को प्राथमिकता के रूप में लेते हैं।

कार्यान्वयन

एक और एरियर का उपयोग कर अधिकतम तत्वों के लिए सी ++ प्रोग्राम

#include <iostream>
#include<algorithm>
#include<unordered_set>

using namespace std;

bool compare(int a, int b)
{
    return a > b;
}
void getMaximizeArray(int arr1[], int arr2[], int n)
{
    int arr3[2*n], j = 0;
    for (int i = 0; i < n; i++)
        arr3[j++] = arr1[i];
    for (int i = 0; i < n; i++)
        arr3[j++] = arr2[i];

    unordered_set<int> SET;

    sort(arr3, arr3 + 2 * n, compare);

    int i = 0;
    while (SET.size() != n)
    {
        if (SET.find(arr3[i]) == SET.end())
            SET.insert(arr3[i]);

        i++;
    }
    j = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr2[i]) != SET.end())
        {
            arr3[j++] = arr2[i];
            SET.erase(arr2[i]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr1[i]) != SET.end())
        {
            arr3[j++] = arr1[i];
            SET.erase(arr1[i]);
        }
    }
    for (int i = 0; i < n; i++)
        arr1[i] = arr3[i];
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    getMaximizeArray(arr1, arr2, n);
    printArray(arr1, n);
}
8 6 5 7 9

एक और एरियर का उपयोग कर अधिकतम तत्वों के लिए जावा प्रोग्राम

import java.util.HashSet;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.lang.*;

class arrayMaximize
{
    public static void getMaximizeArray(int arr1[], int arr2[], int n)
    {
        int arr3[]=new int[2*n];
        int j = 0;
        for (int i = 0; i < n; i++)
            arr3[j++] = arr1[i];
        for (int i = 0; i < n; i++)
            arr3[j++] = arr2[i];


        Arrays.sort(arr3);

        HashSet<Integer> SET=new HashSet<>();

        int i = (2*n)-1;
        while (SET.size() != n)
        {
            if (!SET.contains(arr3[i]))
                SET.add(arr3[i]);

            i--;
        }


        j = 0;
        for (int a = 0; a < n; a++)
        {
            if (SET.contains(arr2[a]))
            {
                arr3[j++] = arr2[a];
                SET.remove(arr2[a]);
            }
        }

        for (int b = 0; b < n; b++)
        {
            if (SET.contains(arr1[b]))
            {
                arr3[j++] = arr1[b];
                SET.remove(arr1[b]);
            }
        }
        for (int c = 0; c < n; c++)
            arr1[c] = arr3[c];
    }
    public static void printArray(int arr[], int n)
    {
        for (int k = 0; k < n; k++)
            System.out.print(arr[k]+" ");
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        getMaximizeArray(arr1, arr2, n);
        printArray(arr1, n);
    }
}
8 6 5 7 9

एक और एरियर का उपयोग करके अधिकतम तत्वों के लिए जटिलता विश्लेषण

समय जटिलता

O (n * लॉग एन) जहां "N" सरणी में तत्वों की संख्या है।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है।

संदर्भ