סדר מחדש מערך כזה ש- arr [i] שווה ל- i


רמת קושי קַל
נשאל לעתים קרובות אקסנצ'ר Adobe אמזון בעברית קנאות פורקיטים Zoho
מערך בליל

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

דוגמה

arr[]={9,4,-1,-1,2,7,8,1,5,-1}
[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

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

אלגוריתם לסידור מחדש של מערך כזה ש- arr [i] שווה ל- i

1. Traverse the array from 0 to n-1(length of the array).
2. Check if arr[i] is greater than equal to 0 and not equal to i.
    1. Swap the elements by doing the following steps.
        1. temp = arr[arr[i]]
        2. arr[arr[i]] = arr[i]
        3. arr[i] = temp
3. Else increase the value of i.
4. Print the array.

הסבר

נותנים לנו מערך of מספרים שלמים בגודל n. הוא יכיל את המספרים בטווח o עד n-1. חלק מה מספרים יכולים להיות חסרים מהטווח. ביקשנו להחליף את כל האלמנטים שבהם arr [i] הופכים לערך כמו i. אם אין מספר במערך עלינו להחליף אותו ל- -1. נניח שיש לנו טווח שבין 0 ל 4. בו יש לנו רק 2 ו -3 במערך, והשאר -1 כאלמנטים, אז עלינו למקם את 2 ו -3 באינדקס כ arr [2] = 2 ו- arr [3] = 3 ושאר המקומות יסומנו כ -1, אם אחד מהמספרים לא נמצא בטווח שבין 0 ל -4.

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

עלינו רק להחליף את הערכים הגדולים משווים ל- 0 ואינם שווים ל- i. כמו כן, אנו מחליפים בתוך המערך בלולאה אחת, בתוך טווח, לכן לקחנו מערך של ערכי arr [i] להחלפה. ולבסוף הדפיסו את הערכים של המערך.

סדר מחדש מערך כזה ש- arr [i] = i

יישום

תוכנית C ++ לסדר מחדש מערך כזה ש- arr [i] שווה ל- i

#include<iostream>

using namespace std;

void arrayRearrange(int arr[], int n)
{
    for (int i = 0; i < n;)
    {
        if (arr[i] >= 0 && arr[i] != i)
        {
            int temp = arr[arr[i]];
            arr[arr[i]] = arr[i];
            arr[i] = temp;
        }
        else
        {
            i++;
        }
    }
    for(int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
}
int main()
{
    int arr[] = {9,4,-1,-1,2,7,8,1,5,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    arrayRearrange(arr,n);

    return 0;
}
-1 1 2 -1 4 5 -1 7 8 9

תוכנית Java לסידור מערך כזה ש- arr [i] שווה ל- i

import java.util.Arrays;

class arrayRearrange
{
    public static void main(String[] args)
    {
        int[] arr = {9,4,-1,-1,2,7,8,1,5,-1};
        for (int i = 0; i < arr.length;)
        {
            if (arr[i] >= 0 && arr[i] != i)
            {
                int temp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] = temp;
            }
            else
            {
                i++;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

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

מורכבות זמן

מכיוון שרק עברנו את המערך, השגנו מורכבות זמן ליניארית. עַל) איפה "N" הוא מספר האלמנטים במערך עבור "סידור מחדש של מערך כך ש- [i] = i" הבעיה.

מורכבות בחלל

האלגוריתם עצמו לוקח O (1) מקום קבוע אך מכיוון שהקלט מאוחסן במערך. אנחנו מקבלים עַל) איפה "N" הוא מספר האלמנטים במערך.