Başqa bir massivdən istifadə edərək elementləri maksimize edin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Fanatics Fourkites
Geyim Sükut çeşidləyiciBaxılıb 20

Tutaq ki, eyni ölçülü iki ədəd ədəd vermişik. Hər iki massivdə müsbət rəqəmlər var. Problem ifadəsi, ikinci massivi prioritet olaraq saxlayan ikinci sıra elementindən istifadə edərək birinci massivi maksimuma çatdırmağı xahiş edir (ikinci sıra elementləri ilk olaraq çıxışda görünməlidir). Bu şəkildə düzəldilmiş massiv içərisində olmalıdır n unikal, lakin hər iki massivin ən böyük elementləri.

misal

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}

Alqoritm

  1. yarat bir array ölçüsü 2 * n.
  2. Əvvəlcə ikinci sıra elementlərini yaradılan bir sıra içərisində, sonra da ilk sıra elementlərini saxlayın.
  3. Dizini artmayan bir ardıcıllıqla sıralayın.
  4. Dizinin n dəyərlərini təyin etmək.
  5. Əvvəlcə array2 götürərək elementin çoxluqda olub olmadığını yoxlayaraq giriş kimi gəldikləri kimi sıraya uyğun yerləşdirin və onları 0-dan üçüncü sırada saxlayın.th index.
  6. Birinci sıra üçün yuxarıdakı əməliyyatı təkrarlayın.
  7. Nəticə dizisini çap edin.

Izahat

Bizdə iki tamsayılar array. İlk massivi bu şəkildə düzəldilmiş massivin əvvəl ikinci sıra elementini, sonra isə birinci cərgəni ehtiva etdiyi şəkildə artırmalıyıq. İçərisində olmalıdır n hər iki massivdən bənzərsiz və ən böyük elementlər. Sifariş saxlanılmalıdır, yəni element əvvəl gəlirsə, ikinci sıra da birinci olmalıdır. Bunu həll etmək üçün 2 * n ölçülü bir sıra yaradın, çünki n ölçüsü kimi verilmiş bir sıra var və hər iki massivin elementlərini də saxlamalıyıq.

İkinci sıra elementlərini əvvəlcə yaratdığımız massivdə saxlayın və sonra ilk massivin elementlərini yaradılan massivdə saxlayın. Bunu qurduğumuz üçün yaradılan dizinin bütün dəyərlərini daxil edəcəyimiz üçün edirik. Çünki bu kodu həll etmək üçün bir dəst istifadə edəcəyik. Yaradılan massivin bütün dəyərlərini dəstə daxil etdikdən sonra. Dizini artmayan bir ardıcıllıqla sıralayacağıq.

Dəyərləri sıra içərisindən n dəfəyə qədər əlavə etmək üçün Set-də yer düzəldəcəyik. N dəfədir, artan ardıcıllıqla sıralanmış bir sıra var, bunun üzərində bəzi əməliyyatlar aparmaq üçün indi ilk n elementə ehtiyacımız var. Set daxil edildikdən sonra setdəki ən böyük n dəyərinə sahibik. İndi bu dəyəri girişə görə sıralarına uyğun olaraq düzəltməliyik, buna görə ilk növbədə serialı keçəcəyik, çünki bu sıra bizim prioritetimizdir. Beləliklə, bir sıra içərisində ikinci sıra elementlərindən birini tapsaq. 0-cı mövqedən yaradılan massivi yeniləyəcəyik və ilk massivi də yoxlayacağıq və üçüncü sıra dəyərlərini yeniləyəcəyik.

İndi array3 dəyərlərini array1 və array1 yazdırın və ikinci serialı prioritet olaraq götürərək birinci massivi maksimum dərəcədə artırırıq.

Həyata keçirilməsi

Başqa bir massivdən istifadə edərək elementləri artırmaq üçün C ++ proqramı

#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

Başqa bir massivdən istifadə edərək elementləri artırmaq üçün Java proqramı

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

Başqa bir massivdən istifadə edərək elementləri maksimize etmək üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n * log n) hara "N" massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır.

References

Translate »