ලබා දී ඇති අරා දෙකකින් උපරිම අරා එක පිළිවෙලට තබා ගැනීම


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇක්සෙන්චර් ඇමේසන් දිල්ලි ෆැක්ට්සෙට් ෆෝකයිට් OYO කාමර Publicis Sapient Zoho
අරා හැෂ්

අපට පූර්ණ සංඛ්‍යා දෙකක් ඇතැයි සිතමු අරාව එකම ප්‍රමාණයේ 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. දෛශික දෙකම එකවර ගමන් කර, දෛශික දෙකේම විශාල අගයන් මූලද්‍රව්‍යයේ සංඛ්‍යාතය සමඟ සිතියමට තල්ලු කරන්න.
  4. නව දෛශික “ප්‍රතිදානය” සාදන්න.
  5. A හි පොදු අංගයක් තිබේදැයි පරීක්ෂා කරන්න සිතියම පළමුව අරාවකින්, පසුව එම මූලද්‍රව්‍යය ප්‍රතිදාන දෛශිකයට එක් කරන්න.
  6. සිතියමක සහ දෙවන පෙළෙහි පොදු මූලද්‍රව්‍යයක් තිබේදැයි පරීක්ෂා කරන්න, එසේ නම්, සංඛ්‍යාතය 1 වන අය තෝරාගෙන ඒවා ප්‍රතිදාන දෛශිකයට එක් කරන්න.
  7. ප්‍රති result ල දෛශික “ප්‍රතිදානය” මුද්‍රණය කරන්න.

පැහැදිලි කිරීම

අරා දෙකම දෛශිකයට හරවා ඒවා අඩු වන අනුපිළිවෙලට වර්ග කරන්න. මේ සමඟ, අපට අරා දෙකේම අගයන් දෛශිකයට ලබා ගත හැකි අතර, දෛශික දෙකෙහිම අනුක්‍රමයකින් අපට විශාල සංඛ්‍යා ඇත. ඉතින්, අපට 'n' තෝරා ගත හැකිය උපරිම අංකය අරා දෙකෙන්ම.

පොදු මූලද්‍රව්‍යයන්ගේ සිද්ධිය හැසිරවීමට නම්, එකවර දෛශික සංසන්දනය කර අරා දෙකෙන්ම උපරිමය තෝරාගෙන ඒවායේ සංඛ්‍යාතය සමඟ සිතියමට ඇතුළත් කරන්න, මේ සමඟ අපට ඇස තබා ගත හැකිය පොදු මූලද්‍රව්‍යයන් වන්න, අපි උපරිම මූලද්‍රව්‍ය n සිතියමට තල්ලු කරන්නෙමු, එක් මූලද්‍රව්‍යයක් එක් වරකට වඩා අපට හමු වුවහොත්, අපි ඒවායේ සංඛ්‍යාතය වැඩි කිරීමට යන අතර ඒවා සිතියමක අතිරේක අංගයක් ලෙස ගණන් නොගනු ඇත, ඒවා වනු ඇත සංඛ්‍යාතය 2, 3 හෝ ඊට වැඩි ලෙස සලකුණු කර ඇත .. එබැවින් පසුකාලීනව ගමන් කිරීමේදී අපට එය නොසලකා හැරිය හැකි අතර පළමු අරාවට ප්‍රමුඛතාවය දිය හැකිය.

අපි අරා සහ සිතියම යන දෙකටම ගමන් කරන්නෙමු. පළමුවෙන්ම, අපි සිතියම සමඟ පළමු අරාව හරහා ගමන් කළ යුතුය, සිතියමක මෙන්ම අරාවෙහි ඇති පොදු මූලද්‍රව්‍යයන් තිබේ නම්, එය ප්‍රති .ලයක් ලෙස අප විසින් නිර්මාණය කරන ලද ප්‍රතිදාන දෛශිකයට තල්ලු කළ යුතුය. පොදු මූලද්‍රව්‍යය ද ප්‍රති result ලයක් ලෙස ගබඩා කළ හැකි බැවින් අපි දෙවන අරාව හරහා ගමන් කරන්නෙමු, එබැවින් මෙහි දෙවන අරා සහ සිතියමේ පොදු අගය සමඟ, එම මූලද්‍රව්‍යයේ සිතියමේ 1 සංඛ්‍යාතයක් තිබේදැයි අපි පරීක්ෂා කරන්නෙමු. , එවිට අපි එය ප්‍රති ve ල දෛශිකයට තල්ලු කරන්නෙමු. අවසාන වශයෙන්, එම දෛශිකය මුද්‍රණය කරන්න.

ක්රියාත්මක කිරීම

ලබා දී ඇති අරා දෙකකින් උපරිම අරා සඳහා 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 ලොග් එන්) එහිදී “N” අරා වල දිග වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” අරා වල දිග වේ.