दुसर्‍या अ‍ॅरेचा वापर करून घटकांची वाढवा


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन कट्टरता फोरकाइट्स
अरे हॅश वर्गीकरण

समजा, आपण समान आकार 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 दोन्ही अ‍ॅरे मधील अद्वितीय आणि महान घटक. ऑर्डर कायम ठेवली पाहिजे की जर घटक प्रथम आला तर तो दुसर्‍या अ‍ॅरेमध्येही प्रथम आला पाहिजे. हे सोडवण्यासाठी आकार २ * n चा अ‍ॅरे बनवा कारण आपल्याकडे आकार n प्रमाणे आरे देण्यात आले आहेत आणि आपल्याला दोन्ही अ‍ॅरेचे घटक संचित करणे आवश्यक आहे.

दुसर्‍या अ‍ॅरेचे घटक प्रथम तयार केलेल्या अ‍ॅरेमध्ये संचयित करा आणि नंतर तयार केलेल्या अ‍ॅरेमध्ये पहिल्या अ‍ॅरेचे घटक संचयित करा. आम्ही हे करत आहोत कारण तयार केलेल्या अ‍ॅरेची सर्व व्हॅल्यूज सेट करण्यासाठी आपण समाविष्ट करणार आहोत. कारण हा कोड सोडवण्यासाठी आम्ही एक सेट वापरणार आहोत. सेटमध्ये तयार केलेल्या अ‍ॅरेची सर्व व्हॅल्यूज समाविष्ट केल्यावर. आपण अ‍ॅरेसिंग अनुक्रमात अ‍ॅरे सॉर्ट करू.

अ‍ॅरे मधून n वेळा पर्यंत व्हॅल्यूज समाविष्ट करण्यासाठी आम्ही सेट मध्ये एक जागा बनवू. एन वेळा म्हणजे आपल्याकडे आधीपासूनच चढत्या क्रमामध्ये क्रमवारी लावलेला अ‍ॅरे आहे, त्यावरील काही ऑपरेशन्स करण्यासाठी आपल्याला आता पहिल्या एन घटकांची आवश्यकता आहे. सेट घातल्यानंतर आमच्याकडे सेटमध्ये सर्वात मोठी एन व्हॅल्यूज आहेत. इनपुट येताच आम्हाला त्यांची व्हॅल्यू त्यांच्या ऑर्डरनुसार व्यवस्थित करण्याची गरज आहे, म्हणजे आपण अ‍ॅरे दुसर्‍या क्रमांकावर जाऊ कारण ते अ‍ॅरे आमचे प्राधान्य आहेत. तर आम्हाला अ‍ॅरेमधील घटकांपैकी दुसरा एखादा सेट मध्ये आढळला. आम्ही 0 व्या स्थानावरून तयार केलेला अ‍ॅरे अद्यतनित करू आणि प्रथम अ‍ॅरे देखील तपासू आणि त्यातील व्हॅल्यू तिसर्‍यामधे अद्यतनित करू.

आता अ‍ॅरे 3 ची व्हॅल्यू अ‍ॅरे 1 आणि प्रिंट अ‍ॅरे 1 मध्ये अपडेट करा आणि अशा प्रकारे आपण दुस ar्या अ‍ॅरेला प्राधान्य म्हणून प्रथम अ‍ॅरेची संख्या वाढवू.

अंमलबजावणी

दुसर्‍या अ‍ॅरेचा वापर करून घटकांच्या वाढीसाठी सी ++ प्रोग्राम

#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) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

संदर्भ