פתרון Leetcode מערך מיון יחסית


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית דה שו eBay Google מיקרוסופט
מערך מפת גיבוב מִיוּן

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

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

דוגמה

Array1 = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99}
Array2 = {5 , 6 , 12}
5 5 6 6 12 1 4 4 7 99

הסבר: סדר האלמנטים במערך השני הוא 5,6 ו- 12. אז הם מופיעים ראשונים במערך התוצאה. האלמנטים האחרים הם 1, 4, 4, 7 ו- 99 הממוינים בסדר שלא יורד.

Array1 = {5 , 4 , 3 , 2 , 1}
Array2 = {1 , 2 , 3 , 4 , 5}
1 2 3 4 5

הסבר: אנו שוב ממיינים את המערך הראשון כך שאלמנטים שלו נמצאים בסדר דומה לזה שבמערך השני.

גישה (השוואה מותאמת אישית)

כאשר אנו משתמשים בשיטת מיון כלשהי, אנו משתמשים בהשוואות בין שני ערכים של מערך כדי להחליט על סדרם היחסי. לדוגמה, במיון בועות, אנו ממשיכים להשוות בין שני אלמנטים סמוכים כך שניתן יהיה להקדים את האלמנט הקטן יותר במערך. ההגדרה של "קטן יותר" באה מגודל או ערך האלמנטים. באופן כללי, המפעיל '<' בודק אם ערך LHS זה פחות מ ערך ה- RHS. שפות תכנות מאפשרות לנו לשנות אופרטורים כאלה עמוס בדרכים רצויות. בזה נשתמש כאן. טכניקות תכנות כאלה בהן אנו משתמשים בשיטות השוואה שונות להחלטת ההזמנה נקראות השוואה מותאמת אישית ואנו משיגים אותה באמצעות משווים מותאמים אישית.

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

vector <int> a = {1 , 2 , 3 , 7 , 4};
sort(a.begin() , a.end() , [&](const int &first , const int &second){
    return first > second;
});

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

אַלגוֹרִיתְם

  1. אתחל מפת חשיש מיקום <> לחשיש את מדדי האלמנטים במערך השני למדדים שלהם
  2. מיין את המערך הראשון, אך עם העברת פונקציית השוואה (באמצעות פונקציית lambda ב- C ++ או ממשק <> ממשק ב- Java)
  3. המשווה עובד על שני ערכים א ו שני באופן הבא:
    1. If מיקום [ראשון] ו מיקום [שנייה] לא קיים:
      1. אנו רוצים שהאלמנט הקטן יותר יבוא קודם, אז חזור ראשון <שניה
    2. If מיקום [ראשון] לא קיים:
      1. אנחנו חוזרים שקר as א אמור לבוא אחר כך במערך
    3. If מיקום [שנייה] לא קיים:
      1. לחזור נכון
    4. לחזור עמדה [ראשונה] <עמדה [שנייה]
  4. הדפיס את התוצאה

יישום פתרון Leetcode של Array Sort Relative

תוכנית C ++

#include <bits/stdc++.h>
using namespace std;

vector<int> relativeSortArray(vector<int>& Array1 , vector<int>& Array2)
{
    unordered_map <int , int> position;

    for(int i = 0 ; i < Array2.size() ; i++)
        position[Array2[i]] = i;

    sort(Array1.begin() , Array1.end() , [&](const int &first , const int &second)
     {
         if(position.find(first) == position.end() && position.find(second) == position.end())
             return first < second;
         if(position.find(first) == position.end())
             return false;
         if(position.find(second) == position.end())
             return true;
         return position[first] < position[second];
     });

    return Array1;
}

int main()
{
    vector <int> a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99} , b = {5 , 6 , 12};
    a = relativeSortArray(a , b);
    for(int &element : a)
        cout << element << " ";
    return 0;
}

תוכנית Java

import java.util.*;

class relative_sort
{
    public static void main(String args[])
    {
        int[] a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99};
        int[] b = {5 , 6 , 12};
        a = relativeSortArray(a , b);
        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }

    static int[] relativeSortArray(int[] Array1, int[] Array2) {
        Hashtable <Integer , Integer> position = new Hashtable<>();
        for(int i = 0 ; i < Array2.length ; i++)
            position.put(Array2[i] , i);

        Integer[] _Array1 = new Integer[Array1.length];
        for(int i = 0 ; i < _Array1.length ; i++)
            _Array1[i] = Array1[i];

        Arrays.sort(_Array1 , new Comparator<Integer>()
                    {
                        public int compare(Integer first , Integer second)
                        {
                            if(position.get(first) == null && position.get(second) == null)
                                return first - second;
                            if(position.get(first) == null)
                                return 1;
                            if(position.get(second) == null)
                                return -1;
                            return position.get(first) - position.get(second);
                        }
                    });

        for(int i = 0 ; i < Array1.length ; i++)
            Array1[i] = _Array1[i];
        return Array1;
    }
}
5 5 6 6 12 1 4 4 7 99

ניתוח מורכבות של פתרון Leetcode מערך-יחס יחסית

מורכבות זמן

O (מקסימום (NlogN, M)) איפה N = גודל המערך הראשון ו- M = גודל המערך השני. אנו מבצעים מעבר יחיד על המערך השני שלוקח זמן O (M) וממיין את המערך הראשון שלוקח זמן O (NlogN) בהנחה שההשוואה מתבצעת בזמן קבוע.

מורכבות בחלל

O (M) כאשר אנו שומרים את מדדי האלמנטים של המערך השני במפת hash.

גישה (מיון ספירה)

בואו נניח Array1 = {1, 2, 2, 2} ו- Array2 = {2, 1}. התחל לחצות את המערך השני. אנו רואים קודם את מספר שלם 2. אם היינו יודעים שיש 3 2 היינו כותבים את הערכים האלה בקלות במערך 1 החל מאינדקס 0. ואז, יש לנו מספר שלם 1 במערך 2. שוב, אם היינו יודעים את התדירות שלו, היינו מאחסנים אותם בקלות לאחר שתיים. באופן דומה, אנו יכולים לאחסן את התדרים של כל האלמנטים במערך 1 ואז להעביר מעבר יחיד של מערך 2, ולכתוב מחדש את האלמנטים במערך 1 בהתאם לתדרים שלהם.

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

אַלגוֹרִיתְם

  1. אתחל מערך: תדר בגודל 1000 לאחסון תדרים של אלמנטים ב- Array1 ו- idx לדעת את המיקום לכתוב שוב אלמנטים במערך 1.
  2. לכל אלמנט במערך 2:
    • בעוד תדר [i]> 0:
      • הקצה מערך 1 [idx] = i
      • idx ++
      • תדר [i] -
  3. לכל אלמנט i בטווח: [0, 4000]:
    • בעוד תדר [i]> 0:
      • הקצה מערך 1 [idx] = i
      • idx ++
      • תדר [i] -
  4. הדפיס את התוצאה

יישום פתרון Leetcode של Array Sort Relative

תוכנית C ++

#include <bits/stdc++.h>
using namespace std;

vector <int> relativeSortArray(vector <int> &Array1 , vector <int> &Array2)
{
    vector <int> frequency(1010 , 0);
    for(int &x : Array1)
        frequency[x]++;

    int idx = 0;

    for(int &i : Array2)
    {
        while(frequency[i] > 0)
            Array1[idx++] = i , frequency[i]--;
    }

    for(int i = 0 ; i < 1010 ; i++)
        while(frequency[i] > 0)
            Array1[idx++] = i , frequency[i]--;

    return Array1;
}

int main()
{
    vector <int> a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99} , b = {5 , 6 , 12};
    a = relativeSortArray(a , b);
    for(int &element : a)
        cout << element << " ";
    return 0;
}

תוכנית Java

import java.util.*;

class relative_sort
{
    public static void main(String args[])
    {
        int[] a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99};
        int[] b = {5 , 6 , 12};
        a = relativeSortArray(a , b);
        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }

    static int[] relativeSortArray(int[] Array1 , int[] Array2)
    {
        int[] frequency = new int[1010];
        for(int i = 0 ; i < 1010 ; i++)
            frequency[i] = 0;

        for(int i = 0 ; i < Array1.length ; i++)
            frequency[Array1[i]]++;

        int idx = 0;

        for(int i = 0 ; i < Array2.length ; i++)
        {
            while(frequency[Array2[i]] > 0)
            {
                Array1[idx++] = Array2[i];
                frequency[Array2[i]]--;
            }
        }

        for(int i = 0 ; i < 1010 ; i++)
            while(frequency[i] > 0)
            {
                Array1[idx++] = i;
                frequency[i]--;
            }

        return Array1;
    }
}
5 5 6 6 12 1 4 4 7 99

ניתוח מורכבות של פתרון Leetcode מערך-יחס יחסית

מורכבות זמן

O (מקסימום (N, M, 1000)) כאשר אנו מאחסנים את תדירות האלמנטים של המערך הראשון במפת hash שלוקח זמן O (N). ואז עבור כל אלמנט במערך השני, אנו ממשיכים לכתוב אותם במערך הראשון עד שהתדרים שלהם הופכים ל 0. סוף סוף אנו בודקים אם כל אלמנט בטווח [0, 4000] ימלא כל אלמנט שמאלי.

מורכבות בחלל

O (1) כאשר אנו משתמשים במרחב קבוע השווה ל- O (1000) במקרה זה כדי לאחסן את תדירות האלמנטים.