أعد ترتيب مصفوفة بحيث تصبح "arr [j]" هي "i" إذا كانت "arr [i]" هي "j"


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

المشكلة بيان

المشكلة "إعادة ترتيب مصفوفة بحيث تصبح" arr [j] "" i "إذا كانت" arr [i] "هي" j "تشير إلى أن لديك "ن" مصفوفة الحجم تحتوي على أعداد صحيحة. تقع الأرقام في المصفوفة في نطاق من 0 إلى n-1. تطلب بيان المشكلة إعادة ترتيب المصفوفة بطريقة تجعل المصفوفة [i] = j تصبح arr [j] = i.

مثال

arr[]={1,3,5,2,0,4}
4 0 3 1 5 2

تفسير

arr [0] = تم تغيير 1 إلى arr [1] = 0

arr [1] = تم تغيير 3 إلى arr [3] = 1

arr [2] = تم تغيير 5 إلى arr [5] = 2

arr [3] = تم تغيير 2 إلى arr [2] = 3

arr [4] = تم تغيير 0 إلى arr [0] = 4

arr [5] = تم تغيير 4 إلى arr [4] = 5

لذلك عند طباعتها ⇒

arr [0] ⇒ arr [1] ⇒ arr [2] ⇒ arr [3] ⇒ arr [4] ⇒ arr [5]

4 0 3 1 5 2

خوارزمية لإعادة ترتيب مصفوفة بحيث تصبح "arr [j]" "i" إذا كانت "arr [i]" هي "j"

1. Traverse the array from 0 to n-1(inclusively).
    1. Do arr [ arr % n ] + = i * n.
2. Then update the value of arr[ i ] =arr[ i ] / n.
3. Print the array.

تفسير

نظرا ل مجموعة of الأعداد الصحيحة. الأرقام التي يحملها تقع في نطاق من 0 إلى n - 1. سنقوم بإعادة ترتيب مجموعة أرقام pf. بحيث تصبح العناصر في المصفوفة مثل arr [j] = i إذا كانت arr [i] = j. هذا يعني أنه إذا كان لدينا بعض القيمة في الموضع ith مثل j ، فقم بتغيير هذه القيمة إلى الموضع j من المصفوفة. أيضًا ، قدمنا ​​عناصر مصفوفة ضمن النطاق من 0 إلى n-1. لذلك لا يمكن أن يتجاوز العدد طول المصفوفة. لذلك يمكن أن يكون مفيدًا عندما نجتاز المصفوفة ، يمكننا أخذ أي قيمة رقمية كمؤشر وإجراء بعض العمليات عليها.

لأننا سنقوم ببعض العمليات على المصفوفة نفسها. سنختار كل عنصر من عناصر المصفوفة ونجد مودولو من arr [i]٪ n ، حيث n هو طول المصفوفة. الآن ، كما ذكرنا سابقًا ، تقع الأرقام في نطاق من 0 إلى n-1. لذلك عندما نكتشف المقياس لأي عدد مع n. لن يتجاوز الرقم الأكبر من فهرس المصفوفة ، لأنه سيتم التعامل مع نمط arr [i]٪ n كفهرس مصفوفة مرة أخرى. ثم نقوم بتخزينها في عملية ضرب i * n. قم بتحديث كل قيمة من قيم modulo كفهرس للصفيف وجمعها مع نفسها.

نحن نقوم بهذا فقط لتخزين وتحديث القيم في المصفوفة إذا كنا سنقوم بإحضارها. علينا فقط تقسيمهم. لأنك إذا ضربت الرقم بـ x وقسمته على x ، فسيصبح الرقم محايدًا كما هو. قم بتحديث arr [i] بقسمة نفس arr [i] على n وتخزينها في arr [i]. بهذه الطريقة نحصل على النتيجة المرجوة. هذه هي طريقة إعادة ترتيب المصفوفة بحيث تصبح "arr [j]" "i" إذا كانت "arr [i]" هي "j".

أعد ترتيب مصفوفة بحيث تصبح "arr [j]" هي "i" إذا كانت "arr [i]" هي "j"

رمز

كود C ++ لإعادة ترتيب مصفوفة بحيث يصبح "arr [j]" "i" إذا كانت "arr [i]" هي "j"

#include<iostream>

using namespace std;

void rearrangeIndexValue(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        arr[arr[i] % n] += i * n;
    }

    for (int i = 0; i < n; i++)
    {
        arr[i] /= n;
    }
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 1,3,5,2,0,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array after modifying :";
    rearrangeIndexValue(arr,n);
    printArray(arr, n);

    return 0;
}
Array after modifying :4 0 3 1 5 2

كود جافا لإعادة ترتيب مصفوفة بحيث يصبح "arr [j]" "i" إذا كانت "arr [i]" هي "j"

class rearrangeArray2
{
    public static void rearrangeIndexValue(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            arr[arr[i] % n] += i * n;
        }
        for (int i = 0; i < n; i++)
        {
            arr[i] /= n;
        }
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = { 1,3,5,2,0,4};
        int n = arr.length;

        rearrangeIndexValue(arr, n);

        System.out.print("Array after modifying : ");
        printArray(arr, n);
    }
}
Array after modifying : 4 0 3 1 5 2

تحليل التعقيد

تعقيد الوقت

O (ن) أين "ن" هو عدد العناصر في المصفوفة. على الرغم من أننا تجاوزنا عناصر المصفوفة مرتين. لذلك ، لا يزال هذا يعتبر تعقيدًا زمنيًا خطيًا فقط.

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في المصفوفة. نظرًا لأننا لم نخزن أي شيء متعلق بكل عنصر وأخذنا مساحة ثابتة فقط. لذا ، فإن التعقيد المكاني للخوارزمية ثابت.