המרת מערך לצורה מופחתת


רמת קושי בינוני
נשאל לעתים קרובות לינקדין Snapchat קסום יאהו
מערך בליל מִיוּן

הצהרת בעיה

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

דוגמה

arr[]={20,10,35,42,8}
2 1 3 4 0

הסבר: עלינו למקם את מספר המערך בצורה המוקטנת בטווח 0 לטווח n-1. אנו יכולים להיראות 8 הוא הקטן ביותר, ולכן הוא 0. 10 הוא הבא אז הוא 1, 20 הוא 2 וכן הלאה.

 

אלגוריתם להמרת מערך לצורה מצומצמת

1. Declare a temporary array of size the same as the original array.
2. Copy all the values of the given array into the declared array.
3. Sort that array in which we have copied the value of the original array.
4. Declare a map and set an integer variable ‘val’ to 0.
5. Traverse the array and store the value of the temp array’ element as a key into the map and a val value and increasing the count of ‘val’ by 1 every time.
6. Traverse the original array from 0 to n-1.
  1. Place the value of the map’s key into the array.
7. Print the original array in which we replace the value of the map.

הסבר

נתנו מערך של מספרים שלמים, עלינו להקטין את המערך באופן שכל מספר במערך המקורי ייקח ערך מטווח 0 עד n-1 מבלי להחמיץ שום ערך מהטווח. פירוש הדבר שאם נתנו 5 מספרים במערך אז נניח את המספר בין 0 ל -4 באופן כללי בכל מיקום של אלמנט במערך המקורי.

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

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

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

המרת מערך לצורה מופחתת

קופונים

קוד C ++ להמרת מערך לצורה מצומצמת

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

using namespace std;

void convert(int arr[], int n)
{
    int temp[n];
    memcpy(temp, arr, n*sizeof(int));

    sort(temp, temp + n);

    unordered_map<int, int> umap;

    int val = 0;
    for (int i = 0; i < n; i++)
        umap[temp[i]] = val++;

    for (int i = 0; i < n; i++)
        arr[i] = umap[arr[i]];
}
void printArr(int arr[], int n)
{
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {20,10,35,42,8};
    int n = sizeof(arr)/sizeof(arr[0]);

    convert(arr, n);
    cout << "Converted Array is : \n";
    printArr(arr, n);
    return 0;
}
Converted Array is :
2 1 3 4 0

 

קוד ג'אווה להמרת מערך לצורה מצומצמת

import java.util.HashMap;
import java.util.Arrays;

class ReducedArray
{
    public static void convert(int arr[], int n)
    {
        int temp[] = arr.clone();

        Arrays.sort(temp);

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

        int val = 0;
        for (int i = 0; i < n; i++)
            umap.put(temp[i], val++);


        System.out.println("Converted Array is : ");
        for (int i = 0; i < n; i++)
        {
            arr[i] = umap.get(arr[i]);
            System.out.print(arr[i] + " ");
        }
    }
    public static void main(String[] args)
    {

        int arr[] = {20,10,35,42,8};
        int n = arr.length;
        convert(arr, n);

    }
}
Converted Array is :
2 1 3 4 0

 

ניתוח מורכבות

מורכבות זמן

We מיון מערך הקלט שלנו. בגלל זה O (n יומן n) איפה "N" הוא גודל המערך.

מורכבות בחלל

מכיוון שאחסנו מערך קלט, השגנו O (n) איפה "N" הוא גודל המערך.