બીજા એરેનો ઉપયોગ કરીને તત્વોને મહત્તમ બનાવો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન કટ્ટરતા ફોરકાઇટ્સ
અરે હેશ સોર્ટિંગ

માની લો, આપણે એ જ કદ n ની બે પૂર્ણાંકોની એરે આપી છે. બંને એરેમાં સકારાત્મક સંખ્યા છે. સમસ્યાનું નિવેદન બીજા એરે એલિમેન્ટનો ઉપયોગ કરીને બીજા એરે એલિમેન્ટનો ઉપયોગ કરીને પ્રથમ એરેને મહત્તમ કરવાનું કહે છે (બીજા એરેના ઘટકો આઉટપુટમાં પ્રથમ દેખાવા જોઈએ). બનેલા એરેમાં સમાવવું જોઈએ 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 * એન.
  2. પ્રથમ બીજા એરે તત્વોને બનાવેલા એરેમાં સંગ્રહિત કરો અને પછી પ્રથમ એરે તત્વો.
  3. એરેને ચડતા ન ક્રમમાં ગોઠવો.
  4. માં એરે ની કિંમતો સંગ્રહિત કરો સમૂહ.
  5. ક્રમમાં ગોઠવો કારણ કે તેઓ પહેલા એરે 2 લઈને ઇનપુટ તરીકે આવે છે અને તપાસ કરે છે કે તેનો તત્વ સેટમાં છે કે નહીં અને તેમને 0 માંથી ત્રીજા એરેમાં સ્ટોર કરો.th અનુક્રમણિકા
  6. પ્રથમ એરે માટે ઉપરોક્ત પ્રક્રિયાને પુનરાવર્તિત કરો.
  7. પરિણામી એરે છાપો.

સમજૂતી

અમારી પાસે બે છે પૂર્ણાંક એરે. આપણે પહેલા એરેને એ રીતે વધારવાની જરૂર છે કે જેથી બનાવેલ એરે પહેલા બીજો એરે એલિમેન્ટ સમાવે અને પછી પ્રથમ એરે. તે હોવું જોઈએ n બંને એરેમાંથી અનન્ય અને મહાન તત્વો. ઓર્ડર જાળવવો જોઈએ જે તે છે કે જો તત્વ પહેલા આવે તો તે બીજા એરેમાં પણ પહેલા આવવું જોઈએ. આને હલ કરવા માટે કદ 2 * n ની એરે બનાવો, કારણ કે આપણી પાસે કદ n ની જેમ એરે આપવામાં આવી છે અને આપણે બંને એરેના તત્વો સંગ્રહિત કરવાની જરૂર છે.

પહેલા બનાવેલા એરેમાં પહેલા એરેના એલિમેન્ટ્સ સ્ટોર કરો અને પછી પહેલા એરેના એલિમેન્ટ્સ બનાવેલા એરેમાં સ્ટોર કરો. અમે આ કરી રહ્યા છીએ કારણ કે આપણે નિર્માણ થયેલ એરેના બધા મૂલ્યો સુયોજિત કરવા જઈશું. કારણ કે આ કોડને હલ કરવા માટે આપણે એક સેટનો ઉપયોગ કરીશું. સમૂહમાં બનાવેલ એરેના બધા મૂલ્યો દાખલ કર્યા પછી. આપણે એરેને ઉતરતા ક્રમમાં ગોઠવીશું.

આપણે એરેમાંથી n સમય સુધીના મૂલ્યો દાખલ કરવા માટે સેટમાં એક સ્થાન બનાવીશું. એન ટાઇમ્સ એ છે કે, આપણી પાસે પહેલેથી જ ચડતા ક્રમમાં ક્રમમાં ગોઠવાયેલ એરે છે, તેના પર કેટલાક ઓપરેશન કરવા માટે આપણને હવે પહેલા એન તત્વોની જરૂર છે. સમૂહના નિવેશ પછી, અમારી પાસે સેટમાં સૌથી મોટી n કિંમતો છે. હવે આપણે તેમના મૂલ્યને તેમના ઓર્ડર મુજબ ગોઠવવાની જરૂર છે કારણ કે તેઓ ઇનપુટ આવે છે, તેથી આપણે પહેલા એરેને પસાર કરીશું કારણ કે એરે અમારી પ્રાધાન્યતા છે. તેથી જો અમને એરેમાંના કોઈપણ તત્વો સેટમાં જોવા મળે છે. આપણે 0 થી પોઝિશનમાંથી બનાવેલ એરેને અપડેટ કરીશું અને સાથે સાથે પ્રથમ એરે પણ તપાસીશું અને એરે ત્રીજામાં તેના વેલ્યુઝને અપડેટ કરીશું.

હવે એરે 3 ની કિંમતોને એરે 1 અને પ્રિન્ટ એરે 1 પર અપડેટ કરો, અને તે રીતે આપણે બીજા એરેને પ્રાધાન્યતા તરીકે લઈ, પ્રથમ એરે મહત્તમ કરીએ છીએ.

અમલીકરણ

બીજા એરેનો ઉપયોગ કરીને તત્વોને મહત્તમ બનાવવા માટે સી ++ પ્રોગ્રામ

#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

બીજા એરેનો ઉપયોગ કરીને મહત્તમ તત્વો માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન * લ nગ એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

સંદર્ભ