ایک صف کو دوبارہ ترتیب دیں اس طرح کہ تیر [i] برابر ہے i  


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایکسینچر ایڈوب ایمیزون فانٹکس فورکائٹس Zoho
لڑی ہیش

"ایک سرنی کو اس طرح سے ترتیب دیں کہ arr [i] = i" مسئلہ میں بتایا گیا ہے کہ آپ کو 0 سے n-1 تک کے عدد کی صف دی جاتی ہے۔ چونکہ تمام عناصر صف میں موجود نہیں ہوسکتے ہیں ، لہذا ان کی جگہ میں -1 موجود ہے۔ پریشانی کا بیان اس طرح سرے کو دوبارہ ترتیب دینے کو کہتا ہے اگر حد کے درمیان ایک بڑی تعداد کسی صف میں موجود نہیں ہے تو پھر اسے -1 کے طور پر نشان زد کریں اور عناصر کو بطور آر آر انجسٹ کریں [i] = i۔

مثال کے طور پر  

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

وضاحت: چونکہ کوئی ہے عنصر حد میں موجود نہیں ہے اس کے بعد ، اس کی جگہ -1 کے ساتھ کی گئی تھی اور یہ کہ صفی انڈیکس خود ہی نمبر کے ساتھ بدل گیا ہے۔

ایک صف کو دوبارہ ترتیب دینے کے لئے الگورتھم اس طرح کہ تیر [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. اس میں او -1 سے لے کر ن -XNUMX کی حد تک کے نمبر ہوں گے۔ میں سے کچھ نمبر غائب ہوسکتے ہیں حد سے ہم نے ان تمام عناصر کو تبدیل کرنے کے لئے کہا ہے جہاں arr [i] جیسے ہی قدر بن جاتے ہیں۔ اگر صف میں کوئی تعداد موجود نہیں ہے تو ہمیں اسے -1 سے بدلنا چاہئے۔ فرض کریں کہ ہمارے پاس 0 سے 4 تک کی حد موجود ہے جس میں ہمارے پاس ایک صف میں صرف 2 اور 3 موجود ہیں ، اور باقی عنصر کی حیثیت سے 1 ہیں ، پھر ہمیں اشارے میں 2 اور 3 رکھنا ہوگا [2] = 2 اور تیر [3] = 3 اور باقی جگہوں کو -1 کے بطور نشان زد کیا جائے گا ، اگر کوئی تعداد 0 سے 4 کی حد میں موجود نہیں ہے۔

یہ بھی دیکھتے ہیں
صف میں بہترین مصنوعات کے ساتھ جوڑی تلاش کریں

ہم نے ایک صف دی ہے۔ ہمارا مرکزی خیال یہ ہے کہ "ایک سرنی کو دوبارہ ترتیب دیں اس طرح کی [i] = i" مسئلہ کو حل کرنے کے لئے صف کے عناصر کو تبدیل کرنا ہے۔ ہم 0 سے n-1 تک صف کو عبور کرنے جارہے ہیں اور "i" کی ہر قیمت کی جانچ کریں گے۔ اگر آرر [i] 0 سے زیادہ ہے تاکہ ہم اس سے بچ سکیں منفی تعداد. وہاں بھی ایک درخواست دینے کی شرط ہے تاکہ لوپ لامحدود نہ ہو ، کیوں کہ ہم دوسرے حصے میں 'i' کی قدر میں اضافہ کر رہے ہیں ، لہذا ہم یہ بھی جانچ رہے ہیں کہ ارے [i] کو بھی "i" کے برابر نہیں ہونا چاہئے۔ تاکہ یہ اچھال کر آگے بڑھ سکے اور مزید اقدار کی جانچ کر سکے۔

ہمیں صرف ان اقدار کو تبدیل کرنے کی ضرورت ہے جو 0 کے برابر ہیں اور i کے برابر نہیں ہیں۔ نیز ، ہم ایک حد میں ایک واحد لوپ کے ساتھ صف میں تبدیل ہو رہے ہیں ، اسی وجہ سے ہم نے ار [[i] اقدار کو تبدیل کرنے کے ل. لیا ہے۔ اور آخر میں سرنی کی وہ اقدار پرنٹ کریں۔

ایک صف کو دوبارہ ترتیب دیں تاکہ arr [i] = i

عمل  

C ++ پروگرام کو دوبارہ ترتیب دینے کے لئے پروگرام اس طرح کہ تیر [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

جاوا پروگرام ایک صف کو دوبارہ ترتیب دینے کے ل Such ایسا ہے کہ ار [[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]

پیچیدگی کا تجزیہ  

وقت کی پیچیدگی

چونکہ ہم صرف صف کو عبور کررہے تھے ، لہذا ہم نے وقتی پیچیدگی حاصل کی۔ O (N) کہاں "N" "ایک صف کو دوبارہ ترتیب دیں جیسے کہ تیر [i] = i" مسئلہ کے ل the صف میں عناصر کی تعداد ہے۔

یہ بھی دیکھتے ہیں
ایک پہاڑی صف میں چوٹی انڈیکس

خلائی پیچیدگی

الگورتھم خود O (1) مستقل جگہ لیتا ہے لیکن چونکہ ان پٹ ایک صف میں محفوظ ہوتا ہے۔ ہم حاصل O (N) کہاں "N" صف میں عناصر کی تعداد ہے۔