ఇచ్చిన రెండు శ్రేణుల నుండి గరిష్ట శ్రేణి ఆర్డర్ కీపింగ్ కీపింగ్


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది యాక్సెంచర్ అమెజాన్ Delhivery ఫాక్ట్‌సెట్ ఫోర్కైట్స్ OYO రూములు పబ్లిసిస్ సపియంట్ జోహో
అర్రే హాష్

మనకు రెండు పూర్ణాంకాలు ఉన్నాయని అనుకుందాం అమరిక అదే పరిమాణం n. రెండు శ్రేణులూ సాధారణ సంఖ్యలను కలిగి ఉంటాయి. సమస్య శ్రేణి రెండు శ్రేణుల నుండి 'n' గరిష్ట విలువలను కలిగి ఉన్న ఫలిత శ్రేణిని ఏర్పరచమని అడుగుతుంది. మొదటి శ్రేణికి ప్రాధాన్యత ఇవ్వాలి (మొదటి శ్రేణి యొక్క అంశాలు మొదట అవుట్‌పుట్‌లో కనిపిస్తాయి). అవుట్పుట్ శ్రేణి ఇచ్చిన రెండు శ్రేణుల నుండి గరిష్ట మూలకాలతో ఉంటుంది, కాని సాధారణ అంశాలు ఒకసారి వచ్చి మొదట శ్రేణికి ప్రాధాన్యత ఇవ్వాలి.

ఉదాహరణ

ఇన్పుట్:

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

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

అవుట్పుట్:

{7, 9, 8, 6, 5}

వివరణ:

7, 9 మొదటి శ్రేణిలోని అంశాలు, తద్వారా ఇది అవుట్‌పుట్‌లో మొదట వస్తుంది.

ఇన్పుట్:

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

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

అవుట్పుట్:

{9, 6, 4}

ఇచ్చిన రెండు శ్రేణుల నుండి గరిష్ట శ్రేణి కోసం అల్గోరిథం కీపింగ్ ఆర్డర్ ఒకే విధంగా ఉంటుంది

  1. రెండు శ్రేణులను వెక్టర్.
  2. ఆరోహణ లేని క్రమంలో రెండు వెక్టర్లను క్రమబద్ధీకరించండి.
  3. రెండు వెక్టర్లను ఒకేసారి ప్రయాణించండి మరియు మూలకం యొక్క ఫ్రీక్వెన్సీతో పాటు రెండు వెక్టర్స్ యొక్క 'n' పెద్ద విలువలను మ్యాప్‌లోకి నెట్టండి.
  4. క్రొత్త వెక్టర్ “అవుట్పుట్” ను సృష్టించండి.
  5. A లో ఒక సాధారణ మూలకం ఉందో లేదో తనిఖీ చేయండి చిహ్నం మొదట శ్రేణిలో, ఆ మూలకాన్ని అవుట్పుట్ వెక్టర్లో చేర్చండి.
  6. మ్యాప్‌లో మరియు శ్రేణి రెండవ భాగంలో కూడా ఒక సాధారణ మూలకం ఉందో లేదో తనిఖీ చేయండి, అప్పుడు, ఫ్రీక్వెన్సీ 1 ఉన్నవారిని ఎన్నుకోండి మరియు వాటిని అవుట్పుట్ వెక్టర్‌లో చేర్చండి.
  7. ఫలిత వెక్టర్ “అవుట్పుట్” ను ప్రింట్ చేయండి.

వివరణ

రెండు శ్రేణులను వెక్టర్‌లోకి మారుస్తుంది మరియు వాటిని తగ్గించే క్రమంలో క్రమబద్ధీకరించండి. దీనితో, మేము రెండు శ్రేణుల విలువలను వెక్టర్‌లోకి పొందవచ్చు మరియు రెండు వెక్టర్లలోని క్రమం లో మొదట పెద్ద సంఖ్యలను కలిగి ఉంటాము. కాబట్టి, మనం 'n' ఎంచుకోవచ్చు గరిష్ట సంఖ్య రెండు శ్రేణుల నుండి.

సాధారణ మూలకాల విషయంలో మనం చేయబోయేది ఏమిటంటే, ఒకేసారి వెక్టర్లను పోల్చడం మరియు రెండు శ్రేణుల నుండి గరిష్టంగా ఎంచుకోవడం మరియు వాటి పౌన frequency పున్యంతో మ్యాప్‌లో ఉంచడం, దీనితో మనం చేయగలిగితే ఒక కన్ను ఉంచవచ్చు సాధారణ మూలకాలుగా ఉండండి, మేము మ్యాప్‌లోకి n గరిష్ట మూలకాలను నెట్టివేస్తాము, ఒకటి కంటే ఎక్కువసార్లు ఒక మూలకాన్ని కనుగొంటే, మేము వాటి ఫ్రీక్వెన్సీని పెంచబోతున్నాము మరియు అవి మ్యాప్‌లో అదనపు మూలకంగా లెక్కించబడవు, అవి ఉంటాయి ఫ్రీక్వెన్సీ 2, 3 లేదా అంతకంటే ఎక్కువ అని గుర్తించబడింది .. కాబట్టి, తరువాతి ట్రావెర్సల్‌లో, మేము దానిని విస్మరించవచ్చు మరియు మొదటి శ్రేణికి ప్రాధాన్యత ఇవ్వవచ్చు.

మేము శ్రేణులు మరియు మ్యాప్ రెండింటినీ దాటబోతున్నాము. మొదట, మేము మొదటి శ్రేణిని మ్యాప్‌తో ప్రయాణించాల్సిన అవసరం ఉంది, మ్యాప్‌లో మరియు శ్రేణిలో కనిపించే సాధారణ అంశాలు ఏమైనా ఉంటే, దాన్ని మనం అవుట్పుట్ వెక్టర్‌లోకి నెట్టాలి, దాని ఫలితంగా మేము సృష్టించాము. సాధారణ మూలకం కూడా ఫలితంలో నిల్వ చేయబడటం వలన మేము రెండవ శ్రేణిని దాటుతాము, కాబట్టి ఇక్కడ రెండవ శ్రేణి మరియు మ్యాప్ నుండి సాధారణ విలువతో పాటు, ఆ మూలకం మ్యాప్‌లో 1 పౌన frequency పున్యం ఉందో లేదో తనిఖీ చేయబోతున్నాం , అప్పుడు మాత్రమే మేము దానిని ఫలిత వెక్టర్‌లోకి నెట్టివేస్తాము. చివరకు, ఆ వెక్టర్‌ను ప్రింట్ చేయండి.

అమలు

ఇచ్చిన రెండు శ్రేణుల నుండి గరిష్ట శ్రేణి కోసం సి ++ ప్రోగ్రామ్ కీపింగ్ ఆర్డర్ అదే

#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” శ్రేణుల పొడవు.

అంతరిక్ష సంక్లిష్టత

పై) (ఇక్కడ  “N” శ్రేణుల పొడవు.