दुई दिइएको एर्रेबाट अधिकतम एर्रे समान क्रम राख्दै


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एक्सेंचर अमेजन दिल्लीवरी तथ्य फोरकाइट्स OYO कोठा पब्लिसिस सेपिएन्ट Zoho
एरे हैश

मानौं हामीसँग दुईवटा पूर्णांकहरू छन् array समान आकार एन को। दुबै एर्रेमा सामान्य संख्या पनि हुन सक्छ। समस्या कथन परिणाम एरे गठन गर्न सोध्छ कि एरे दुबै 'n' अधिकतम मानहरू समावेश गर्दछ। पहिलो एर्रे प्राथमिकतामा हुनुपर्दछ (पहिलो एर्रेको तत्व आउटपुटमा पहिले देखा पर्दछ)। आउटपुट एरे दुबै दिएका एर्रेबाट अधिकतम तत्वहरूको हुन्छ तर साधारण तत्वहरू एक पटक आउनुपर्दछ र एर्रेलाई प्राथमिकता दिनुपर्नेछ।

उदाहरणका

इनपुट:

int arr1 [] = {3,7,9,1,4,,, १,}}

int arr2 [] = {2,8,6,5,3,,, १,}}

उत्पादन:

{7, 9, 8, 6, 5}

व्याख्या:

As, पहिलो एरेमा एलिमेन्टहरू हुन्, त्यसैले आउटपुटमा पहिलो आउँछ।

इनपुट:

int arr1 [] = {9,3,2,,, १,}}

int arr2 [] = {6,4,1,,, १,}}

उत्पादन:

{9, 6, 4}

दुई दिइएका एर्रेबाट समान क्रम राखेर अधिकतम एर्रेको लागि एल्गोरिथ्म

  1. दुबै एर्रे लाई। मा रूपान्तरण गर्नुहोस् सदिश.
  2. दुबै भेक्टरहरुलाई क्रमबद्ध गर्नुहोस् गैर आरोही अनुक्रममा।
  3. दुबै भेक्टरको एकैसाथ ट्र्यावर्स गर्नुहोस्, र दुबै भेक्टरको 'एन' ठूलो मानहरूलाई एन्टिमेन्ट फ्रिक्वेन्सीको साथ नक्सामा धकेल्नुहोस्।
  4. नयाँ भेक्टर "आउटपुट" सिर्जना गर्नुहोस्।
  5. त्यहाँ एक सामान्य तत्व छ कि छैन जाँच गर्नुहोस् नक्सा र एर्रेमा पहिले पनि, त्यसपछि, तत्वलाई आउटपुट भेक्टरमा थप्नुहोस्।
  6. जाँच गर्नुहोस्, यदि त्यहाँ नक्सामा र एर्रे दोस्रोमा पनि एलिमेन्ट तत्व छ, तब, जसको फ्रिक्वेन्सी १ छ तिनीहरूलाई चयन गर्नुहोस्, र तिनीहरूलाई आउटपुट भेक्टरमा थप्नुहोस्।
  7. परिणाम भेक्टर "आउटपुट" प्रिन्ट गर्नुहोस्।

स्पष्टीकरण

दुबै एरेहरू भेक्टरमा रूपान्तरण गर्दै घट्दै क्रममा क्रमबद्ध गर्नुहोस्। यससँग हामी दुबै एर्रेको मान भेक्टरमा प्राप्त गर्न सक्छौं र हामी दुबै भेक्टरमा अनुक्रममा पहिले ठूलो संख्यामा छौं। त्यसोभए हामी 'एन' छनौट गर्न सक्छौं अधिकतम संख्या दुबै एर्रेबाट।

हामी के गर्न जाँदैछौं सामान्य तत्वहरूको केस ह्यान्डल गर्नका लागि, एकसाथ भेक्टरहरूसँग तुलना गर्ने र एर्रे दुबैबाट अधिकतम लिने, र यसलाई उनीहरूको फ्रिक्वेन्सीको साथ नक्सामा राख्नुपर्दछ, यदि हामी यहाँ पाउन सक्दछौं भने आँखा कायम राख्न सक्छौं। सामान्य तत्वहरू हुनुहोस्, हामी नक्सामा n अधिकतम तत्त्वहरू धकेल्दै छौं, यदि हामीले एक भन्दा बढी तत्त्वहरू फेला पार्‍यौं भने, हामी तिनीहरूको फ्रिक्वेन्सी बढाउने छौं र तिनीहरूलाई नक्सामा थप तत्वका रूपमा गणना गरिनेछैन, तिनीहरू हुनेछन्। फ्रिक्वेन्सी २, or वा अधिकको रूपमा चिन्ह लगाइएको छ। त्यसो भए पछि ट्रभर्सलमा हामी यसलाई बेवास्ता गर्न सक्दछौं र पहिलो एरेलाई प्राथमिकता दिन सक्छौं।

हामी दुबै एर्रे र नक्शालाई ट्र्याभर्स गर्न जाँदैछौं। सर्वप्रथम, हामीले पहिलो एरेलाई नक्शाको साथ पार गर्नु पर्छ, यदि कुनै सामान्य तत्वहरू नक्सामा साथै एर्रेमा फेला पर्‍यो भने हामीले त्यसलाई आउटपुट भेक्टरमा धकेल्नु पर्छ, जुन हामीले परिणाम स्वरूप सिर्जना गरेका छौं। त्यसो भए हामी दोस्रो एर्रे पार गर्नेछौं किनकि साझा एलिमेन्ट पनि परिणाममा भण्डार हुन सक्दछ, त्यसैले यहाँ दोस्रो एर्रे र नक्शाबाट समान मानको साथ हामी जाँच गर्न गइरहेछौं कि त्यो एन्टिमेन्टमा नक्सामा १ फ्रिक्वेन्सी छ कि छैन। , तब मात्र हामी यसलाई नतिजा भेक्टरमा धकेल्नेछौं। र अन्तमा, त्यो भेक्टर प्रिन्ट गर्नुहोस्।

कार्यान्वयन

C ++ कार्यक्रम दुई दिइने एर्रेबाट समान ओइन्डि Order गर्दै अर्डरबाट अधिकतम एर्रेको लागि

#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 log n) जहाँ "N" एर्रे को लम्बाई हो।

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रे को लम्बाई हो।