تنظیم مجدد آرایه به گونه ای که arr [i] برابر با i باشد


سطح دشواری ساده
اغلب در Accenture خشت آمازون متعصبان فورکایت 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 باشد تا بتوانیم از آن جلوگیری کنیم اعداد منفی. در آنجا شرایطی نیز اعمال می شود که حلقه نامحدود نباشد ، زیرا ما در بخش دیگر مقدار "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

برنامه جاوا برای تنظیم مجدد آرایه به گونه ای که 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" تعداد عناصر موجود در آرایه برای مسئله "تنظیم مجدد آرایه به گونه ای است که arr [i] = i" مشکل باشد.

پیچیدگی فضا

الگوریتم خود فضای ثابت O (1) را می گیرد اما از آنجا که ورودی در یک آرایه ذخیره می شود. ما گرفتیم بر) جایی که "N" تعداد عناصر آرایه است.