מערך מקסימלי משני מערכים נתונים תוך שמירה על סדר זהה


רמת קושי בינוני
נשאל לעתים קרובות אקסנצ'ר אמזון בעברית מסירה סט עובדות פורקיטים חדרי OYO פובליסיס סאפיינט Zoho
מערך בליל

נניח שיש לנו שני מספרים שלמים מערך באותו גודל n. שני המערכים יכולים להכיל גם מספרים נפוצים. הצהרת הבעיה מבקשת ליצור את המערך המתקבל המכיל את הערכים המרביים 'n' משני המערכים. יש לתת עדיפות למערך הראשון (אלמנטים של המערך הראשון צריכים להופיע תחילה בפלט). מערך הפלט יהיה של מקסימום אלמנטים משני המערכים הנתונים, אך אלמנטים משותפים צריכים להגיע פעם אחת ולתעדף את המערך תחילה.

דוגמה

קלט:

int arr1 [] = {3,7,9,1,4}

int arr2 [] = {2,8,6,5,3}

פלט:

{7, 9, 8, 6, 5}

הסבר:

כמו 7, 9 הם האלמנטים במערך הראשון, כך שהוא מגיע ראשון בפלט.

קלט:

int arr1 [] = {9,3,2}

int arr2 [] = {6,4,1}

פלט:

{9, 6, 4}

אלגוריתם למערך מקסימאלי משני מערכים נתונים תוך שמירה על סדר זהה

  1. להמיר את שני המערכים ל וקטור.
  2. ממיין את שני הווקטורים ברצף שאינו עולה.
  3. חצו את שני הווקטורים בו זמנית, ודחפו 'n' ערכים גדולים יותר של שני הווקטורים למפה יחד עם תדר האלמנט.
  4. צור "פלט" וקטור חדש.
  5. בדוק אם יש אלמנט משותף ב- מַפָּה וגם במערך תחילה, ואז הוסף את האלמנט הזה לווקטור הפלט.
  6. בדוק אם יש אלמנט משותף במפה וגם במערך שני, ואז בחר את אלה שתדירותם 1 והוסף אותם לווקטור הפלט.
  7. הדפס את "פלט" הווקטור שהתקבל.

הסבר

להמיר את שני המערכים לווקטור ולמיין אותם בסדר יורד. בעזרת זה, אנו יכולים להכניס את הערכים של שני המערכים לווקטור ויש לנו מספרים גדולים יותר ברצף בשני הווקטורים. אז אנחנו יכולים לבחור 'n' המספר המירבי משני המערכים.

כדי לטפל במקרה של אלמנטים נפוצים, מה שאנחנו הולכים לעשות הוא להשוות בו זמנית את הווקטורים ולבחור את המקסימום משני המערכים, ולהכניס אותו למפה בתדירות שלהם, ובכך נוכל לשמור על עין אם יש להיות אלמנטים נפוצים, נדחוף n אלמנטים מרביים למפה, אם מצאנו אלמנט אחד יותר מפעם אחת, אנחנו רק הולכים להגדיל את התדירות שלהם והם לא ייחשבו כאלמנט נוסף במפה, מסומן כתדר 2, 3 ומעלה .. לכן, במעבר מאוחר יותר, אנו יכולים להתעלם ממנו ויכולים לתת עדיפות למערך הראשון.

אנו הולכים לחצות את שניהם, את המערכים והמפה. ראשית, עלינו לחצות את המערך הראשון עם המפה, אם אחד מהאלמנטים הנפוצים שנמצאים במפה כמו גם במערך, עלינו לדחוף אותו לתוך וקטור הפלט, אותו יצרנו כתוצאה. ואז נחצה את המערך השני מכיוון שהאלמנט המשותף יכול להיות מאוחסן גם בתוצאה, ולכן כאן יחד עם הערך המשותף מהמערך השני ומפה, אנחנו הולכים לבדוק אם לאלמנט הזה יש תדר 1 במפה אז רק אנחנו נדחוף אותו לווקטור המתקבל. ולסיום, הדפיסו את הווקטור הזה.

יישום

תוכנית C ++ למערך מקסימלי משני מערכים נתונים תוך שמירה על סדר זהה

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;

void makeGreaterFirstArray(int A[], int B[], int n)
{
    vector<int> V1(A, A+n);
    vector<int> V2(B, B+n);
    sort(V1.begin(), V1.end(), greater<int>());
    sort(V2.begin(), V2.end(), greater<int>());

    unordered_map<int, int> MAP;
    int i = 0, j = 0;
    while (MAP.size() < n)
    {
        if (V1[i] >= V2[j])
        {
            MAP[V1[i]]++;
            i++;
        }
        else
        {
            MAP[V2[j]]++;
            j++;
        }
    }
    vector<int> output;
    for (int i = 0; i < n; i++)
        if (MAP.find(A[i]) != MAP.end())
            output.push_back(A[i]);

    for (int i = 0; i < n; i++)
        if (MAP.find(B[i]) != MAP.end() && MAP[B[i]] == 1)
            output.push_back(B[i]);

    for (int i = 0; i < n; i++)
        cout << output[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    makeGreaterFirstArray(arr1, arr2, n);
    return 0;
}
7 9 8 6 5

תוכנית Java למערך מקסימלי משני מערכים נתונים תוך שמירה על סדר זהה

import java.util.Collections;
import java.util.Vector;
import java.util.HashMap;
import java.util.Arrays;
import java.util.stream.Collectors;

class findsubarray
{
    public static void makeGreaterFirstArray(int []A, int []B, int n)
    {
        Vector<Integer> V1 = new Vector<>();
        Vector<Integer> V2 = new Vector<>();

        Integer[] I1 = Arrays.stream( A ).boxed().toArray( Integer[]::new );
        Integer[] I2 = Arrays.stream( B ).boxed().toArray( Integer[]::new );


        Collections.addAll(V1, I1);
        Collections.addAll(V2, I2);

        Collections.sort(V1, Collections.reverseOrder());
        Collections.sort(V2, Collections.reverseOrder());


        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int i = 0, j = 0;
        while (MAP.size() < n)
        {
            if (V1.get(i) >= V2.get(j))
            {
                if(MAP.containsKey(V1.get(i)))
                {
                    MAP.put(V1.get(i), MAP.get(V1.get(i))+1);
                    i++;
                }
                else
                {
                    MAP.put(V1.get(i),1);
                    i++;
                }
            }
            else
            {
                if(MAP.containsKey(V2.get(j)))
                {
                    MAP.put(V2.get(j), MAP.get(V2.get(j))+1);
                    j++;
                }
                else
                {
                    MAP.put(V2.get(j),1);
                    j++;
                }
            }
        }
        Vector<Integer> output = new Vector<Integer>();

        for (int a = 0; a < n; a++)
            if (MAP.containsKey(A[a]))
                output.add(A[a]);

        for (int b = 0; b < n; b++)
            if (MAP.containsKey(B[b]) && MAP.get(B[b])==1)
                output.add(B[b]);


        System.out.println(output);
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        makeGreaterFirstArray(arr1, arr2, n);
    }
}
[7, 9, 8, 6, 5]

ניתוח מורכבות למערך מרבי משני מערכים נתונים תוך שמירה על סדר זהה

מורכבות זמן

O (n יומן n) איפה "N" הוא אורך המערכים.

מורכבות בחלל

O (n) איפה "N" הוא אורך המערכים.