තවත් අරා භාවිතා කරමින් මූලද්‍රව්‍ය උපරිම කරන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් උන්මත්තකයෝ ෆෝකයිට්
අරා හැෂ් වර්ග කිරීම

අපි එකම ප්‍රමාණයේ පූර්ණ සංඛ්‍යා දෙකක් ලබා දී ඇතැයි සිතමු. අරා දෙකේම ධනාත්මක සංඛ්‍යා අඩංගු වේ. ගැටළු ප්‍රකාශය දෙවන අරාව ප්‍රමුඛතාවය ලෙස තබා ගනිමින් දෙවන අරාව මූලද්‍රව්‍යය භාවිතා කරමින් පළමු අරාව උපරිම කිරීමට ඉල්ලා සිටී (දෙවන අරාවේ මූලද්‍රව්‍ය ප්‍රතිදානයේදී පළමුව දිස්විය යුතුය). එසේ සාදන ලද අරාවෙහි අඩංගු විය යුතුය n අරා දෙකේම අද්විතීය නමුත් විශාලතම අංග.

උදාහරණයක්

arr1[] = {3,7,9,1,4}
arr2[] = {2,8,6,5,3}
{8, 6, 5, 7, 9}
arr1[] = {9,3,2}
arr2[] = {6,4,1}
{6, 4, 9}

ඇල්ගොරිතම

  1. නිර්මාණය කරන්න අරාව ප්‍රමාණය 2 * n.
  2. පළමුව දෙවන අරාව මූලද්‍රව්‍ය සාදන ලද අරාවකට ගබඩා කර පළමු අරා මූලද්‍රව්‍ය ගබඩා කරන්න.
  3. අරා නොයන අනුපිළිවෙලකට වර්ග කරන්න.
  4. අරාවෙහි n අගයන් කට්ටලයක්.
  5. පළමුවෙන් අරාව 2 ගෙන එහි මූලද්‍රව්‍යය කට්ටලයේ තිබේදැයි පරීක්ෂා කර ඒවා 0 සිට තුන්වන අරාවෙහි ගබඩා කර ඒවා ආදානය ලෙස පිළිවෙලට සකසන්න.th දර්ශකය.
  6. පළමු අරාව සඳහා ඉහත ක්‍රියාවලිය නැවත කරන්න.
  7. ප්‍රති result ල අරාව මුද්‍රණය කරන්න.

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

අපිට දෙන්නෙක් ඉන්නවා නිඛිල අරාව. අප විසින් සාදන ලද අරාවෙහි දෙවන අරා මූලද්‍රව්‍යය පළමුව සහ පසුව පළමු අරාව අඩංගු වන පරිදි පළමු අරාව උපරිම කළ යුතුය. එය අඩංගු විය යුතුය n අරා දෙකෙන්ම අද්විතීය හා විශාලතම අංග. අනුපිළිවෙල පවත්වා ගත යුතුය, එනම් මූලද්‍රව්‍යය පළමුව පැමිණේ නම් එය දෙවන අරාවෙහි පළමු තැනට පැමිණිය යුතුය. මෙය නිරාකරණය කිරීම සඳහා 2 * n ප්‍රමාණයේ අරාවක් සාදන්න, මන්ද අපට n ප්‍රමාණයෙන් ලබා දී ඇති අරාවක් ඇති අතර අපට අරා දෙකේම මූලද්‍රව්‍ය ගබඩා කළ යුතුය.

දෙවන අරාවෙහි මූලද්‍රව්‍යයන් පළමුව අප විසින් සාදන ලද අරාව වෙත ගබඩා කර පළමු අරාවේ මූලද්‍රව්‍ය සාදන ලද අරාව වෙත ගබඩා කරන්න. අප මෙය සිදු කරන්නේ අප විසින් සාදන ලද අරාවෙහි සියලු අගයන් සැකසීමට ඇතුළු කිරීමට යන බැවිනි. මෙම කේතය විසඳීම සඳහා අපි කට්ටලයක් භාවිතා කිරීමට යන්නේ. සාදන ලද අරාවෙහි සියලු අගයන් කට්ටලයට ඇතුළත් කිරීමෙන් පසුව. අපි අරාව ආරෝහණ නොවන අනුපිළිවෙලකට වර්ග කරමු.

අරාවේ සිට අගයන් n වාරයක් දක්වා ඇතුළත් කිරීමට අපි සෙට් හි ස්ථානයක් සාදන්නෙමු. N වේලාවන් සඳහා, අප සතුව දැනටමත් ආරෝහණ නොවන අනුපිළිවෙලින් වර්ග කර ඇත, අපට දැන් එහි පළමු n මූලද්‍රව්‍ය අවශ්‍ය වන්නේ එය මත යම් මෙහෙයුම් සිදු කිරීමට ය. කට්ටලය ඇතුළත් කිරීමෙන් පසුව, අපට කට්ටලයේ විශාලතම n අගයන් ඇත. දැන් අපි එම අගය ඒවායේ අනුපිළිවෙලට අනුව ඒවා ආදානය අනුව සකස් කළ යුතුය, එබැවින් අපි අරාව දෙවනුව ගමන් කරන්නේ පළමුව එම අරාව අපගේ ප්‍රමුඛතාවය වන බැවිනි. එබැවින්, අරාවෙහි දෙවන මූලද්‍රව්‍යයන් කට්ටලයක් තුළ අපට හමු වූවා නම්. අපි 0 වන ස්ථානයේ සිට සාදන ලද අරාව යාවත්කාලීන කරන අතර පළමු අරාවද පරීක්ෂා කර එහි අගයන් තෙවන අරා යාවත්කාලීන කරන්නෙමු.

දැන් array3 හි අගයන් array1 වෙත යාවත්කාලීන කර array1 මුද්‍රණය කරන්න, එවිට අපි පළමු අරාව උපරිම කරගනිමින් දෙවන අරාව ප්‍රමුඛතාවයක් ලෙස ගනිමු.

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

තවත් අරාවක් භාවිතා කරමින් මූලද්‍රව්‍ය උපරිම කිරීම සඳහා C ++ වැඩසටහන

#include <iostream>
#include<algorithm>
#include<unordered_set>

using namespace std;

bool compare(int a, int b)
{
    return a > b;
}
void getMaximizeArray(int arr1[], int arr2[], int n)
{
    int arr3[2*n], j = 0;
    for (int i = 0; i < n; i++)
        arr3[j++] = arr1[i];
    for (int i = 0; i < n; i++)
        arr3[j++] = arr2[i];

    unordered_set<int> SET;

    sort(arr3, arr3 + 2 * n, compare);

    int i = 0;
    while (SET.size() != n)
    {
        if (SET.find(arr3[i]) == SET.end())
            SET.insert(arr3[i]);

        i++;
    }
    j = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr2[i]) != SET.end())
        {
            arr3[j++] = arr2[i];
            SET.erase(arr2[i]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr1[i]) != SET.end())
        {
            arr3[j++] = arr1[i];
            SET.erase(arr1[i]);
        }
    }
    for (int i = 0; i < n; i++)
        arr1[i] = arr3[i];
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    getMaximizeArray(arr1, arr2, n);
    printArray(arr1, n);
}
8 6 5 7 9

තවත් අරා භාවිතා කරමින් මූලද්‍රව්‍ය උපරිම කිරීම සඳහා ජාවා වැඩසටහන

import java.util.HashSet;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.lang.*;

class arrayMaximize
{
    public static void getMaximizeArray(int arr1[], int arr2[], int n)
    {
        int arr3[]=new int[2*n];
        int j = 0;
        for (int i = 0; i < n; i++)
            arr3[j++] = arr1[i];
        for (int i = 0; i < n; i++)
            arr3[j++] = arr2[i];


        Arrays.sort(arr3);

        HashSet<Integer> SET=new HashSet<>();

        int i = (2*n)-1;
        while (SET.size() != n)
        {
            if (!SET.contains(arr3[i]))
                SET.add(arr3[i]);

            i--;
        }


        j = 0;
        for (int a = 0; a < n; a++)
        {
            if (SET.contains(arr2[a]))
            {
                arr3[j++] = arr2[a];
                SET.remove(arr2[a]);
            }
        }

        for (int b = 0; b < n; b++)
        {
            if (SET.contains(arr1[b]))
            {
                arr3[j++] = arr1[b];
                SET.remove(arr1[b]);
            }
        }
        for (int c = 0; c < n; c++)
            arr1[c] = arr3[c];
    }
    public static void printArray(int arr[], int n)
    {
        for (int k = 0; k < n; k++)
            System.out.print(arr[k]+" ");
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        getMaximizeArray(arr1, arr2, n);
        printArray(arr1, n);
    }
}
8 6 5 7 9

තවත් අරාවක් භාවිතා කරමින් මූලද්‍රව්‍ය උපරිම කිරීම සඳහා සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (n * log n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

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

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

ආශ්රිත