നൽകിയിരിക്കുന്ന രണ്ട് അറേകളിൽ നിന്നുള്ള പരമാവധി അറേ ഓർഡർ സൂക്ഷിക്കുന്നു


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ഓട്ടോമോട്ടീവ് ആമസോൺ ദില്ലി ഫാക്റ്റ്സെറ്റ് ഫോർകൈറ്റുകൾ OYO മുറികൾ പബ്ലിസിസ് സാപിയന്റ് Zoho
അറേ ഹാഷ്

നമുക്ക് രണ്ട് പൂർണ്ണസംഖ്യകളുണ്ടെന്ന് കരുതുക ശ്രേണി ഒരേ വലുപ്പമുള്ള n. രണ്ട് അറേകളിലും സാധാരണ സംഖ്യകളും അടങ്ങിയിരിക്കാം. രണ്ട് അറേകളിൽ‌ നിന്നും 'n' പരമാവധി മൂല്യങ്ങൾ‌ അടങ്ങിയിരിക്കുന്ന ഫലമായുണ്ടാകുന്ന അറേ രൂപീകരിക്കുന്നതിന് പ്രശ്ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു. ആദ്യ അറേയ്‌ക്ക് മുൻ‌ഗണന നൽകണം (ആദ്യ അറേയുടെ ഘടകങ്ങൾ .ട്ട്‌പുട്ടിൽ ആദ്യം ദൃശ്യമാകും). നൽകിയിരിക്കുന്ന രണ്ട് അറേകളിൽ നിന്നുമുള്ള elements ട്ട്‌പുട്ട് അറേ പരമാവധി ഘടകങ്ങളാണെങ്കിലും സാധാരണ ഘടകങ്ങൾ ഒരിക്കൽ വന്ന് അറേയ്‌ക്ക് മുൻ‌ഗണന നൽകണം.

ഉദാഹരണം

ഇൻപുട്ട്:

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

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

ഔട്ട്പുട്ട്:

{7, 9, 8, 6, 5}

വിശദീകരണം:

7, 9 എന്നത് ആദ്യ അറേയിലെ ഘടകങ്ങളാണ്, അതിനാൽ the ട്ട്‌പുട്ടിൽ ഇത് ആദ്യം വരുന്നു.

ഇൻപുട്ട്:

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

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

ഔട്ട്പുട്ട്:

{9, 6, 4}

തന്നിരിക്കുന്ന രണ്ട് അറേകളിൽ നിന്നുള്ള പരമാവധി അറേയ്ക്കുള്ള അൽഗോരിതം ഓർഡർ സൂക്ഷിക്കുന്നു

  1. രണ്ട് അറേകളും വെക്ടർ.
  2. ആരോഹണക്രമത്തിൽ രണ്ട് വെക്ടറുകളും അടുക്കുക.
  3. രണ്ട് വെക്റ്ററുകളും ഒരേസമയം സഞ്ചരിക്കുക, മൂലകത്തിന്റെ ആവൃത്തിയോടൊപ്പം രണ്ട് വെക്ടറുകളുടെയും 'n' വലിയ മൂല്യങ്ങൾ മാപ്പിലേക്ക് നീക്കുക.
  4. ഒരു പുതിയ വെക്റ്റർ “.ട്ട്‌പുട്ട്” സൃഷ്‌ടിക്കുക.
  5. A ൽ ഒരു പൊതു ഘടകമുണ്ടോയെന്ന് പരിശോധിക്കുക ഭൂപടം ആദ്യം ഒരു അറേയിലും, element ട്ട്‌പുട്ട് വെക്ടറിലേക്ക് ആ ഘടകം ചേർക്കുക.
  6. ഒരു മാപ്പിൽ ഒരു പൊതു ഘടകമുണ്ടോയെന്നും രണ്ടാമത്തെ ശ്രേണിയിലും ഉണ്ടോയെന്ന് പരിശോധിക്കുക, തുടർന്ന്, ആവൃത്തി 1 ആയവരെ തിരഞ്ഞെടുത്ത് അവയെ ve ട്ട്‌പുട്ട് വെക്ടറിൽ ചേർക്കുക.
  7. ഫലമായുണ്ടാകുന്ന വെക്റ്റർ “.ട്ട്‌പുട്ട്” പ്രിന്റുചെയ്യുക.

വിശദീകരണം

രണ്ട് അറേകളും വെക്റ്ററിലേക്ക് പരിവർത്തനം ചെയ്യുകയും ക്രമം കുറയ്ക്കുന്നതിന് ക്രമീകരിക്കുകയും ചെയ്യുക. ഇതുപയോഗിച്ച്, നമുക്ക് രണ്ട് അറേകളുടെയും മൂല്യങ്ങൾ വെക്റ്ററിലേക്ക് നേടാൻ കഴിയും, കൂടാതെ രണ്ട് വെക്റ്ററുകളിലെയും ഒരു ശ്രേണിയിൽ ആദ്യം നമുക്ക് വലിയ സംഖ്യകളുണ്ട്. അതിനാൽ, നമുക്ക് 'n' തിരഞ്ഞെടുക്കാം പരമാവധി എണ്ണം രണ്ട് അറേകളിൽ നിന്നും.

പൊതുവായ ഘടകങ്ങളുടെ കാര്യം കൈകാര്യം ചെയ്യാൻ, ഒരേസമയം വെക്റ്ററുകളെ താരതമ്യം ചെയ്യുകയും രണ്ട് അറേകളിൽ നിന്നും പരമാവധി എടുക്കുകയും അവയുടെ ആവൃത്തി ഉപയോഗിച്ച് മാപ്പിൽ ഇടുകയും ചെയ്യുക, ഇതുപയോഗിച്ച് നമുക്ക് ഒരു കണ്ണ് നിലനിർത്താൻ കഴിയും പൊതുവായ ഘടകങ്ങളായിരിക്കുക, ഞങ്ങൾ മാപ്പിലേക്ക് n പരമാവധി ഘടകങ്ങൾ തള്ളിവിടും, ഒന്നിലധികം ഘടകങ്ങൾ ഞങ്ങൾ ഒന്നിലധികം തവണ കണ്ടെത്തിയാൽ, ഞങ്ങൾ അവയുടെ ആവൃത്തി വർദ്ധിപ്പിക്കാൻ പോകുന്നു, മാത്രമല്ല അവ ഒരു മാപ്പിലെ അധിക ഘടകമായി കണക്കാക്കില്ല, അവ ആയിരിക്കും ആവൃത്തി 2, 3 അല്ലെങ്കിൽ അതിൽ കൂടുതൽ എന്ന് അടയാളപ്പെടുത്തി .. അതിനാൽ, പിന്നീടുള്ള ട്രാവെർസലിൽ, നമുക്ക് ഇത് അവഗണിക്കാം, ഒപ്പം ആദ്യ അറേയ്ക്ക് മുൻ‌ഗണന നൽകാനും കഴിയും.

ഞങ്ങൾ ശ്രേണികളും മാപ്പും രണ്ടും സഞ്ചരിക്കാൻ പോകുന്നു. ആദ്യം, മാപ്പിനൊപ്പം ആദ്യത്തെ അറേയിലൂടെ സഞ്ചരിക്കേണ്ടതുണ്ട്, ഒരു മാപ്പിലും അതുപോലെ ഒരു അറേയിലും കാണപ്പെടുന്ന പൊതുവായ ഘടകങ്ങൾ ഉണ്ടെങ്കിൽ, ഞങ്ങൾ അത് ve ട്ട്‌പുട്ട് വെക്ടറിലേക്ക് തള്ളേണ്ടതുണ്ട്, അതിന്റെ ഫലമായി ഞങ്ങൾ സൃഷ്ടിച്ചു. സാധാരണ മൂലകവും ഫലത്തിൽ‌ സംഭരിക്കാൻ‌ കഴിയുന്നതിനാൽ‌ ഞങ്ങൾ‌ രണ്ടാമത്തെ അറേയിലൂടെ സഞ്ചരിക്കും, അതിനാൽ‌ ഇവിടെ രണ്ടാമത്തെ അറേയിൽ‌ നിന്നും മാപ്പിൽ‌ നിന്നുമുള്ള പൊതു മൂല്യത്തിനൊപ്പം, ആ ഘടകത്തിന് മാപ്പിൽ‌ 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 ലോഗ് n) എവിടെ “N” അറേകളുടെ നീളം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേകളുടെ നീളം.