दोन दिलेल्या अ‍ॅरेमधून जास्तीत जास्त अ‍ॅरे समान ठेवणे


अडचण पातळी मध्यम
वारंवार विचारले ऐक्सचर ऍमेझॉन दिल्लीवारी फॅक्टसेट फोरकाइट्स ओयओ रूम्स पब्लिसिस सेपिएंट Zoho
अरे हॅश

समजा आपल्याकडे दोन पूर्णांक आहेत अॅरे समान आकाराचे एन. दोन्ही अ‍ॅरेमध्ये सामान्य संख्या देखील असू शकतात. प्रॉब्लेम स्टेटमेंटने एरे दोघांकडील 'एन' जास्तीत जास्त मूल्ये असलेल्या परिणामी अ‍ॅरे तयार करण्यास सांगितले. प्रथम अ‍ॅरेला प्राधान्य दिले जावे (आउटपुटमध्ये प्रथम अ‍ॅरेचे घटक प्रथम दिसले पाहिजेत). आउटपुट अ‍ॅरे दिलेल्या दोन्ही अ‍ॅरेमधून जास्तीत जास्त घटकांचा असेल परंतु सामान्य घटक एकदा येऊन अ‍ॅरेला प्रथम प्राधान्य दिले पाहिजे.

उदाहरण

इनपुट:

इंट एआर 1 [] = {3,7,9,1,4}

इंट एआर 2 [] = {2,8,6,5,3}

आउटपुट:

{7, 9, 8, 6, 5}

स्पष्टीकरण:

,, हे पहिल्या अ‍ॅरेमधील घटक आहेत जेणेकरून ते आउटपुटमध्ये प्रथम येईल.

इनपुट:

इंट एआर 1 [] = {9,3,2}

इंट एआर 2 [] = {6,4,1}

आउटपुट:

{9, 6, 4}

ऑर्डर कीपिंग ऑर्डर समान दिलेल्या दोन अ‍ॅरेमधून मॅक्सिममम अ‍ॅरेसाठी अल्गोरिदम

  1. दोन्ही अ‍ॅरे मध्ये रुपांतरित करा वेक्टर.
  2. दोन्ही सदिशांना चढत्या क्रमाने क्रमवारी लावा.
  3. दोन्ही वेक्टर्सचा एकाच वेळी आढावा घ्या आणि त्या घटकांच्या वारंवारतेसह नकाशामध्ये दोन्ही वेक्टरची मोठी व्हॅल्यू 'n' वर ढकलून घ्या.
  4. नवीन वेक्टर “आउटपुट” तयार करा.
  5. ए मध्ये एक सामान्य घटक आहे की नाही ते तपासा नकाशा आणि प्रथम अ‍ॅरेमध्ये देखील नंतर ते घटक आउटपुट वेक्टरमध्ये जोडा.
  6. नकाशामध्ये आणि इतर अ‍ॅरेमध्ये देखील सामान्य घटक असल्यास ते तपासा, ज्यांची वारंवारता 1 आहे त्यांना निवडा आणि त्यांना आउटपुट वेक्टरमध्ये जोडा.
  7. परिणामी वेक्टर “आउटपुट” प्रिंट करा.

स्पष्टीकरण

अ‍ॅरेचे दोन्ही रूपांतर वेक्टरमध्ये करणे आणि त्यांना कमी क्रमाने क्रमवारीत लावणे. याद्वारे आपण दोन्ही अ‍ॅरेची व्हॅक्टर वेक्टर मध्ये मिळवू शकतो आणि दोन्ही वेक्टरच्या अनुक्रमात आपल्याकडे आधी मोठी संख्या आहे. तर आपण 'n' निवडू शकतो. जास्तीत जास्त संख्या दोन्ही अ‍ॅरेमधून.

आम्ही काय करणार आहोत या घटकांचे प्रकरण हाताळण्यासाठी, एकाच वेळी वेक्टरची तुलना करणे आणि दोन्ही अ‍ॅरेमधून जास्तीत जास्त निवडणे आणि त्यांच्या वारंवारतेसह नकाशामध्ये ठेवणे शक्य आहे. सामान्य घटक व्हा, आम्ही नकाशामध्ये n जास्तीत जास्त घटक ढकलत आहोत, जर आम्हाला एकापेक्षा जास्त घटक आढळले तर आम्ही त्यांची वारंवारता वाढवणार आहोत आणि ते नकाशामध्ये अतिरिक्त घटक म्हणून मोजले जाणार नाहीत, ते असतील फ्रिक्वेन्सी 2, 3 किंवा त्याहून अधिक म्हणून चिन्हांकित केली आहे .. तर नंतरच्या आक्रमणामध्ये आपण त्याकडे दुर्लक्ष करू आणि प्रथम अ‍ॅरेला प्राधान्य देऊ शकतो.

आम्ही अ‍ॅरे आणि नकाशा या दोघांनाही मागे सोडणार आहोत. प्रथम, आम्हाला नकाशासह प्रथम अ‍ॅरे ओलांडणे आवश्यक आहे, जर नकाशामध्ये तसेच अ‍ॅरेमध्ये कोणतेही सामान्य घटक आढळले तर आम्हाला त्यास आउटपुट वेक्टरमध्ये ढकलणे आवश्यक आहे, जे आम्ही परिणामी तयार केले. नंतर आम्ही दुसर्‍या अ‍ॅरेला मागे टाकू कारण सामान्य घटक देखील परिणामी मध्ये संग्रहित केला जाऊ शकतो, तर येथे दुसर्‍या अ‍ॅरे आणि नकाशावरील सामान्य मूल्यासह आम्ही त्या घटकाची नकाशे मध्ये 1 ची वारंवारता असल्याचे तपासणार आहोत. , तर केवळ आम्ही त्यास परिणामी वेक्टरमध्ये ढकलणार आहोत. आणि शेवटी, तो वेक्टर प्रिंट करा.

अंमलबजावणी

ऑर्डर समान ठेवून दिलेल्या दोन अ‍ॅरेमधून जास्तीत जास्त अ‍ॅरेसाठी सी ++ प्रोग्राम

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;

void makeGreaterFirstArray(int A[], int B[], int n)
{
    vector<int> V1(A, A+n);
    vector<int> V2(B, B+n);
    sort(V1.begin(), V1.end(), greater<int>());
    sort(V2.begin(), V2.end(), greater<int>());

    unordered_map<int, int> MAP;
    int i = 0, j = 0;
    while (MAP.size() < n)
    {
        if (V1[i] >= V2[j])
        {
            MAP[V1[i]]++;
            i++;
        }
        else
        {
            MAP[V2[j]]++;
            j++;
        }
    }
    vector<int> output;
    for (int i = 0; i < n; i++)
        if (MAP.find(A[i]) != MAP.end())
            output.push_back(A[i]);

    for (int i = 0; i < n; i++)
        if (MAP.find(B[i]) != MAP.end() && MAP[B[i]] == 1)
            output.push_back(B[i]);

    for (int i = 0; i < n; i++)
        cout << output[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    makeGreaterFirstArray(arr1, arr2, n);
    return 0;
}
7 9 8 6 5

दोन दिलेल्या अ‍ॅरे कडून कीपिंग ऑर्डर समान कडून जावा प्रोग्राम

import java.util.Collections;
import java.util.Vector;
import java.util.HashMap;
import java.util.Arrays;
import java.util.stream.Collectors;

class findsubarray
{
    public static void makeGreaterFirstArray(int []A, int []B, int n)
    {
        Vector<Integer> V1 = new Vector<>();
        Vector<Integer> V2 = new Vector<>();

        Integer[] I1 = Arrays.stream( A ).boxed().toArray( Integer[]::new );
        Integer[] I2 = Arrays.stream( B ).boxed().toArray( Integer[]::new );


        Collections.addAll(V1, I1);
        Collections.addAll(V2, I2);

        Collections.sort(V1, Collections.reverseOrder());
        Collections.sort(V2, Collections.reverseOrder());


        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int i = 0, j = 0;
        while (MAP.size() < n)
        {
            if (V1.get(i) >= V2.get(j))
            {
                if(MAP.containsKey(V1.get(i)))
                {
                    MAP.put(V1.get(i), MAP.get(V1.get(i))+1);
                    i++;
                }
                else
                {
                    MAP.put(V1.get(i),1);
                    i++;
                }
            }
            else
            {
                if(MAP.containsKey(V2.get(j)))
                {
                    MAP.put(V2.get(j), MAP.get(V2.get(j))+1);
                    j++;
                }
                else
                {
                    MAP.put(V2.get(j),1);
                    j++;
                }
            }
        }
        Vector<Integer> output = new Vector<Integer>();

        for (int a = 0; a < n; a++)
            if (MAP.containsKey(A[a]))
                output.add(A[a]);

        for (int b = 0; b < n; b++)
            if (MAP.containsKey(B[b]) && MAP.get(B[b])==1)
                output.add(B[b]);


        System.out.println(output);
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        makeGreaterFirstArray(arr1, arr2, n);
    }
}
[7, 9, 8, 6, 5]

ऑर्डर कीपिंग ऑर्डर समान दिलेल्या दोन अ‍ॅरेमधून जास्तीत जास्त अ‍ॅरेसाठी गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन लॉग एन) जेथे “एन” अ‍ॅरेची लांबी आहे.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरेची लांबी आहे.