ელემენტების მაქსიმიზაცია სხვა მასივის გამოყენებით


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon ფანატიკა Fourkites
Array Hash დახარისხება

ვთქვათ, ჩვენ მივეცით იგივე ზომის 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 * n.
  2. პირველი შეინახეთ მასივის მეორე ელემენტები შექმნილ მასივში და შემდეგ ჯერ მასივის ელემენტები.
  3. დაალაგეთ მასივი არა აღმავალი თანმიმდევრობით.
  4. შეინახეთ მასივის n მნიშვნელობები მითითებული.
  5. მოაწესრიგეთ ისინი თანმიმდევრობით, რადგან ისინი შეიტანენ მას შემდეგ, რაც მასივი 2 მიიღება და შეამოწმეთ არის თუ არა მისი ელემენტი სიმრავლეში და შეინახეთ ისინი მესამე მასივში 0 – დანth ინდექსი.
  6. გაიმეორეთ ზემოთ მოცემული პროცესი პირველი მასივისთვის.
  7. დაბეჭდე შედეგიანი მასივი.

განმარტება

ჩვენ ორი გვაქვს რიცხვები მასივი. ჩვენ უნდა მაქსიმალურად გავზარდოთ პირველი მასივი ისე, რომ ასე ჩამოყალიბებული მასივი შეიცავდეს ჯერ მასივის მეორე ელემენტს და შემდეგ პირველ მასივს. ეს უნდა შეიცავდეს n უნიკალური და უდიდესი ელემენტები ორივე მასივიდან. წესრიგი უნდა იყოს დაცული, თუ ელემენტი მოდის პირველ რიგში, ის ასევე უნდა იყოს მეორე მასივში პირველი. ამის გადასაჭრელად შევქმნათ 2 * n ზომის მასივი, რადგან მასივი გვაქვს n ზომის მიხედვით და უბრალოდ უნდა შევინახოთ ორივე მასივის ელემენტები.

შეინახეთ მეორე მასივის ელემენტები, პირველ რიგში, ჩვენს მიერ შექმნილ მასივში და შემდეგ შეინახეთ პირველი მასივის ელემენტები შექმნილ მასივში. ჩვენ ამას ვაკეთებთ, რადგან ჩვენ ვაყენებთ შექმნილი მასივის ყველა მნიშვნელობის ჩასმას დასაყენებლად. რადგან ამ კოდის გადასაჭრელად ჩვენ ვაყენებთ კომპლექტს. სიმრავლეში შექმნილი მასივის ყველა მნიშვნელობის ჩასმის შემდეგ. მასივს დალაგებთ არა აღმავალი თანმიმდევრობით.

ჩვენ დავაყენებთ ადგილს Set- ში მასივის მნიშვნელობების ჩასმა n დრომდე. N დრო არის, ჩვენ უკვე გვაქვს დახარისხებული მასივი არა აღმავალი თანმიმდევრობით, ახლა გვჭირდება პირველი n ელემენტები ახლა მასზე გარკვეული ოპერაციების გასაკეთებლად. Set– ის ჩასმის შემდეგ, ჩვენ გვაქვს უდიდესი n მნიშვნელობები. ახლა ჩვენ უნდა მოვაწყოთ ეს მნიშვნელობა მათი თანმიმდევრობით, როდესაც ისინი შედიან, ასე რომ, მასივს მეორეზე გადავხედავთ, რადგან ეს მასივი ჩვენი პრიორიტეტია. ასე რომ, თუ მასივის მეორე ელემენტი აღმოვაჩინეთ ნაკრებში. ჩვენ განვაახლებთ იმ მასივს, რომელიც შეიქმნა 0-ე პოზიციიდან და ასევე შეამოწმეთ პირველი მასივი, ასევე განაახლეთ მისი მნიშვნელობები მესამე მასივში.

ახლა განაახლეთ მასივის 3 მნიშვნელობები მასივში 1 და დაბეჭდეთ მასივი 1 და ასე მაქსიმალურად ვადიდებთ პირველ მასივს, პრიორიტეტად ვიღებთ მეორე მასივს.

განხორციელება

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

Java პროგრამა ელემენტების მაქსიმიზაციისთვის სხვა მასივის გამოყენებით

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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

ლიტერატურა