تعظيم العناصر باستخدام مصفوفة أخرى


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون المتعصبون فوركايتس
مجموعة مزيج فرز

لنفترض أننا قدمنا ​​مصفوفة من الأعداد الصحيحة لها نفس الحجم 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. قم بتخزين قيم n للمصفوفة في ملف طقم.
  5. رتبهم بالترتيب كما يأتون كمدخلات عن طريق أخذ array2 أولاً والتحقق مما إذا كان عنصرها موجودًا في المجموعة وتخزينها في المصفوفة الثالثة من 0th مؤشر.
  6. كرر العملية المذكورة أعلاه للمصفوفة الأولى.
  7. اطبع المصفوفة الناتجة.

تفسير

لدينا اثنان الأعداد الصحيحة مجموعة. نحتاج إلى تكبير المصفوفة الأولى بحيث تحتوي المصفوفة التي تم تشكيلها على عنصر المصفوفة الثاني أولاً ثم المصفوفة الأولى. يجب أن تحتوي على n عناصر فريدة وأكبر من كلا المصفوفتين. يجب الحفاظ على الترتيب الذي إذا كان العنصر يأتي أولاً ، فيجب أن يأتي أولاً في المصفوفة الثانية. لحل هذه المشكلة ، أنشئ مصفوفة بحجم 2 * n لأن لدينا مصفوفة بالحجم n ونحتاج فقط إلى تخزين عناصر كلتا المصفوفتين.

قم بتخزين عناصر المصفوفة الثانية أولاً في المصفوفة التي أنشأناها ثم قم بتخزين عناصر المصفوفة الأولى في المصفوفة التي تم إنشاؤها. نحن نقوم بذلك لأننا سنقوم بإدراج جميع قيم المصفوفة التي تم إنشاؤها لتعيينها. لأنه لحل هذا الرمز ، سنستخدم مجموعة. بعد إدخال جميع قيم المصفوفة التي تم إنشاؤها في المجموعة. سنقوم بفرز المصفوفة في تسلسل غير تصاعدي.

سنضع مكانًا في المجموعة لإدخال القيم من المصفوفة حتى عدد n من المرات. عدد مرات N من أجل ، لدينا بالفعل المصفوفة المرتبة في تسلسل غير تصاعدي ، نحتاج فقط إلى العناصر n الأولى الآن لإجراء بعض العمليات عليها. بعد إدراج Set ، لدينا أكبر قيم n في المجموعة. نحتاج الآن إلى ترتيب هذه القيمة وفقًا لترتيبها عند إدخالها ، لذلك سنجتاز المصفوفة ثانيًا أولاً لأن هذه المصفوفة هي أولويتنا. لذلك إذا وجدنا أيًا من عناصر المصفوفة الثانية موجودة في المجموعة. سنقوم بتحديث المصفوفة التي تم إنشاؤها من الموضع 0 ، وكذلك التحقق من وجود المصفوفة الأولى أيضًا وتحديث قيمها في المصفوفة الثالثة.

الآن قم بتحديث قيم المصفوفة 3 إلى array1 وطباعة المصفوفة 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 (ن) أين "ن" هو عدد العناصر في الصفيف.

المراجع