अ‍ॅरेची पुनर्रचना करा अशी एरर [i] i च्या बरोबरीची आहे


अडचण पातळी सोपे
वारंवार विचारले ऐक्सचर अडोब ऍमेझॉन कट्टरता फोरकाइट्स Zoho
अरे हॅश

“अ‍ॅर अशा अ‍ॅरेची पुनर्रचना करा [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 पूर्णांक आकाराचे एन. यात ओ-एन -1 श्रेणीतील संख्या असेल. काही संख्या गहाळ होऊ शकतात श्रेणीतून. आम्ही सर्व घटक बदलण्यास सांगितले आहे जेथे एर [i] i म्हणून मूल्य बनतात. अ‍ॅरेमध्ये कोणतीही संख्या नसल्यास ती -1 ने बदलली पाहिजे. समजा आपल्याकडे ० ते from अशी श्रेणी आहे ज्यामध्ये आपल्याकडे अ‍ॅरेमध्ये फक्त २ आणि present अस्तित्त्वात आहेत आणि उरलेले घटक -१ आहेत, तर आपल्याला एरर म्हणून निर्देशांकात २ आणि place लावावे लागेल [२] = २ आणि अरर []] = and आणि उर्वरित जागा ० ते from पर्यंतच्या श्रेणीत नसल्यास उर्वरित जागा -0 म्हणून चिन्हांकित केल्या जातील.

आम्ही अ‍ॅरे दिली आहे. आमची मुख्य कल्पना अ‍ॅरे [i] = i "समस्येचे निराकरण करण्यासाठी अ‍ॅरेचे घटक स्वॅप करणे आहे. आपण अ‍ॅरे 0 ते n-1 पर्यंत पार करू आणि “i” ची प्रत्येक व्हॅल्यू तपासणार आहोत. जर अरर [i] 0 पेक्षा मोठे असेल तर आम्ही त्यास टाळू शकतो नकारात्मक संख्या. तिथे अर्ज करण्याची एक अट देखील आहे जेणेकरून लूप अनंत होणार नाही, कारण आपण 'आय' ची व्हॅल्यू दुसर्‍या भागात वाढवत आहोत. म्हणून आपण हेही तपासत आहोत की अरर [i] देखील “i” च्या बरोबर नाही. जेणेकरून ते वगळू आणि पुढे जाऊ शकेल आणि पुढील व्हॅल्यूज तपासू शकतील.

आपल्याकडे फक्त त्या व्हॅल्यूज स्वॅप करणे आवश्यक आहे जे 0 च्या बडीपेक्षा जास्त आहेत आणि i बरोबर नाहीत. तसेच, आपण रेंजमध्ये एका लूपसह withinरेमध्ये अदलाबदल करीत आहोत. म्हणूनच आपण अ‍ॅर व्हेल्यूजचा अ‍ॅरे [i] स्वॅप करण्यासाठी घेतला आहे. आणि शेवटी अ‍ॅरेच्या त्या व्हॅल्यूज प्रिंट करा.

अशा अ‍ॅरेची पुन्हा व्यवस्था करा [i] = i

अंमलबजावणी

अ‍ॅरेची पुनर्रचना करण्यासाठी सी ++ प्रोग्राम असा एर [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

अ‍ॅरेची पुनर्रचना करण्यासाठी जावा प्रोग्रॅम अशा एर [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]

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

आम्ही फक्त अ‍ॅरेचा मागोवा घेत असल्याने आम्ही रेषीय वेळ गुंतागुंत साधली. ओ (एन) जेथे “एन” “अ‍ॅरेची पुनर्व्यवस्थित करा जसे की एर [i] = i” समस्येसाठी अ‍ॅरेमधील घटकांची संख्या आहे.

स्पेस कॉम्प्लेक्सिटी

अल्गोरिदम स्वतः ओ (1) स्थिर जागा घेते परंतु इनपुट अ‍ॅरेमध्ये संचयित केल्यामुळे. आम्ही मिळवा ओ (एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.