إعادة ترتيب مصفوفة بحيث تكون arr [i] مساوية لـ i


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

"إعادة ترتيب مصفوفة بحيث تنص مشكلة 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] متساوية

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 الأعداد الصحيحة من الحجم سيحتوي على الأرقام الموجودة في النطاق من 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 فيمكننا تجنب أرقام سلبية. هناك أيضًا شرط يتم تطبيقه هناك بحيث لا تصبح الحلقة غير محدودة ، حيث إننا نزيد قيمة "i" في جزء آخر ، لذلك نحن نتحقق أيضًا من أن 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] متساويًا

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" هو عدد العناصر في المصفوفة لـ "إعادة ترتيب مصفوفة بحيث تكون arr [i] = i" مشكلة.

تعقيد الفضاء

تأخذ الخوارزمية نفسها مساحة ثابتة O (1) ولكن حيث يتم تخزين الإدخال في صفيف. نحن نحصل على) أين "N" هو عدد العناصر في الصفيف.