ትዕዛዝ ከተሰጠ ከሁለት የተሰጡ ድርድሮች ከፍተኛው ድርድር  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ Accenture አማዞን አቅርቦት ፋርስት አራት ኪይትስ ኦዮ ክፍሎች Publicis Sapient ቮሆ
ሰልፍ ሃሽ

ሁለት ኢንቲጀሮች አሉን እንበል ደርድር ተመሳሳይ መጠን 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. በ ውስጥ አንድ የተለመደ ንጥረ ነገር ካለ ያረጋግጡ ካርታ እንዲሁም በመጀመሪያ በድርድር ውስጥ ፣ ያንን ንጥረ ነገር ወደ ውፅዓት ቬክተር ውስጥ ይጨምሩ።
  6. ይፈትሹ ፣ በካርታ ውስጥ እና በድርድር ሰከንድ ውስጥ አንድ የተለመደ አካል ካለ ፣ ከዚያ ብዛታቸው 1 የሆኑትን ይምረጡ እና ወደ ውፅዓት ቬክተር ውስጥ ያክሏቸው።
  7. የውጤቱን ቬክተር “ውፅዓት” ያትሙ።
ተመልከት
አነስተኛ ቅንፍ መቀልበሻዎች

ማስረጃ  

ሁለቱንም ድርድሮች ወደ ቬክተር በመቀየር በቅደም ተከተል በቅደም ተከተል ፡፡ በዚህ አማካኝነት የሁለቱም ድርድር እሴቶችን ወደ ቬክተር ውስጥ ማግኘት እንችላለን እናም በመጀመሪያ በሁለቱም ቬክተር ውስጥ በቅደም ተከተል ትላልቅ ቁጥሮች አሉን ፡፡ ስለዚህ ፣ ‘n’ ን መምረጥ እንችላለን ከፍተኛ ቁጥር ከሁለቱም ድርድር ፡፡

እኛ የምንሰራቸውን የጋራ አካላት ጉዳይ ለማስተናገድ ፣ ቬክተሮችን በማወዳደር እና ከሁለቱም ድርድሮች ከፍተኛውን በመምረጥ እና ከድግግሞቻቸው ጋር ወደ ካርታው ውስጥ በማስቀመጥ ፣ በዚህ ከቻልን ዐይን መከታተል እንችላለን ፡፡ የተለመዱ አባሎች ይሁኑ ፣ እኛ n ከፍተኛውን ንጥረ ነገሮች ወደ ካርታው እንገፋፋቸዋለን ፣ ከአንድ በላይ አባሎችን ካገኘን ፣ ድግግሞሾቻቸውን እናሳድጋለን እናም በካርታ ውስጥ እንደ ተጨማሪ አካል አይቆጠሩም ፣ እነሱ ይሆናሉ እንደ ተደጋጋሚነት 2 ፣ 3 ወይም ከዚያ በላይ ምልክት ተደርጎበታል .. ስለዚህ ፣ በኋላ በሚመጣው የትራንስፖርት እንቅስቃሴ ውስጥ ፣ ችላ ልንለው እና የመጀመሪያውን ድርድር ቅድሚያ መስጠት እንችላለን።

እኛ ሁለቱንም ፣ ዝግጅቶቹን እና ካርታውን እናቋርጣለን ፡፡ በመጀመሪያ ፣ የመጀመሪያውን ድርድር ከካርታው ጋር ማለፍ ያስፈልገናል ፣ በካርታ ውስጥም ሆነ በአንድ ድርድር ውስጥ ከተገኙት የተለመዱ ንጥረ ነገሮች ውስጥ በውጤቱ ወደፈጠርነው የውጤት ቬክተር መግፋት አለብን ፡፡ ከዚያ የጋራው ንጥረ ነገር በውጤቱ ውስጥ ሊከማች ስለሚችል ሁለተኛውን ድርድር እናልፋለን ፣ ስለሆነም እዚህ ከሁለተኛው ድርድር እና ከካርታ ካለው የጋራ እሴት ጋር ፣ ይህ ንጥረ ነገር በካርታው ውስጥ 1 ድግግሞሽ እንዳለው እንፈትሻለን ፣ ከዚያ ወደ ውጤቱ ቬክተር የምንገፋው እኛ ብቻ ነን ፡፡ እና በመጨረሻም ያንን ቬክተር ያትሙ።

ተመልከት
በአንድ ረድፍ ውስጥ የሚቀርቡ ከፍተኛው ተከታታይ ቁጥሮች

አፈጻጸም  

የ C ++ ፕሮግራም ለከፍተኛው ድርድር ከሁለት ከተሰጡት ድርድሮች ቅደም ተከተል ጠብቆ ማቆየት

#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]

ትዕዛዝ ከተሰጠ ከሁለት የተሰጡ ድርድሮች ለከፍተኛው ድርድር ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (n log n) የት “N” የዝግጅት ርዝመት ነው።

ተመልከት
በድርድር ውስጥ ከፍተኛው ርቀት

የቦታ ውስብስብነት

ሆይ (n) የት “N” የዝግጅት ርዝመት ነው።