एक सरणी को फिर से व्यवस्थित करें जैसे कि 'गिरफ्तार [जे]' मैं 'हो जाता है अगर' गिरफ्तार [i] '' जी 'है


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Delhivery कुलिजा नगरो संचालित टाइम्स इंटरनेट यात्रा
ऐरे

समस्या का विवरण

समस्या "किसी सरणी को फिर से व्यवस्थित करें जैसे कि 'ए.आर. "N" पूर्णांक युक्त आकार का आकार। सरणी में संख्या 0 से n-1 की सीमा में हैं। समस्या कथन सरणी को इस तरह से पुनर्व्यवस्थित करने के लिए कहता है कि सरणी [i] = j को गिरफ्तार किया जाता है [j] = i।

उदाहरण

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

व्याख्या

arr [0] = 1 को गिरफ्तार करने के लिए बदल दिया जाता है [1] = 0

arr [1] = 3 को गिरफ्तार करने के लिए बदल दिया जाता है [3] = 1

arr [2] = 5 को गिरफ्तार करने के लिए बदल दिया जाता है [5] = 2

arr [3] = 2 को गिरफ्तार करने के लिए बदल दिया जाता है [2] = 3

arr [4] = 0 को गिरफ्तार करने के लिए बदल दिया जाता है [0] = 4

arr [5] = 4 को गिरफ्तार करने के लिए बदल दिया जाता है [4] = 5

इसलिए जब ⇒ छपा

गिरफ्तार [0] ⇒ गिरफ्तारी [1] ⇒ गिरफ्तारी [२] ⇒ गिरफ्तार [३] ⇒ गिरफ्तार [४] ⇒ गिरफ्तार [५]

4 0 3 1 5 2

किसी सरणी को पुनर्व्यवस्थित करने के लिए एल्गोरिथ्म ऐसा है कि 'गिरफ्तार [जे]' मैं 'हो जाता है अगर' गिरफ्तार [i] '' '' '

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 array। ताकि एरे में तत्व ऐसे हो जाएँ जो गिरफ्तारी [j] = i अगर गिरफ्तारी हो [i] = j। इस प्रकार इसका मतलब है कि यदि हमारे पास j के रूप में ith स्थिति में कुछ मूल्य है, तो उस मान को किसी सरणी की jth स्थिति में बदल दें। इसके अलावा, हमने 0 से n-1 तक की श्रेणी में सरणी तत्व दिए हैं। तो संख्या किसी सरणी की लंबाई से अधिक नहीं हो सकती। तो यह फायदेमंद हो सकता है जब हम सरणी को पीछे छोड़ते हैं, हम किसी भी संख्या के मूल्य को एक सूचकांक के रूप में ले सकते हैं और उस पर कुछ संचालन कर सकते हैं।

क्योंकि हम सरणी पर ही कुछ ऑपरेशन करने जा रहे हैं। हम प्रत्येक ऐरे तत्व को चुनेंगे और खोजेंगे प्रपत्र गिरफ्तारी [i]% n की, जहां n एक सरणी की लंबाई है। अब, जैसा कि हमने पहले उल्लेख किया है कि संख्या 0 से n-1 की सीमा में हैं। इसलिए जब हम n के साथ किसी भी संख्या के मॉडुलो का पता लगाते हैं। यह सरणी के एक सूचकांक से अधिक संख्या से अधिक नहीं होगा, क्योंकि गिरफ्तारी का मॉडुलो [i]% n को फिर से सरणी के सूचकांक के रूप में माना जाएगा। और फिर हम इसे i * n के गुणन में संग्रहीत करते हैं। सरणी के एक सूचकांक के रूप में मोडुलो के प्रत्येक मूल्य को अपडेट करें और इसे स्वयं के साथ जोड़ दें।

यदि हम उन्हें लाने जा रहे हैं तो हम सरणी में मानों को संग्रहीत और अद्यतन करने के लिए बस ऐसा कर रहे हैं। हमें बस उन्हें विभाजित करना है। क्योंकि यदि आप संख्या को x से गुणा करते हैं और x के साथ विभाजित करते हैं तो संख्या तटस्थ हो जाएगी क्योंकि यह है। एक ही गिरफ्तारी [i] को n से विभाजित करके गिरफ्तारी [i] को अद्यतन करें और इसे गिरफ्तार करने के लिए इसे स्टोर करें [i]। इस तरह, हम वांछित परिणाम प्राप्त करेंगे। इस तरह से एक सरणी को पुनर्व्यवस्थित करने के लिए इस तरह के 'गिरफ्तारी [जे]' मैं 'अगर' गिरफ्तार [i] '' जी 'हो जाता है।

एक सरणी को फिर से व्यवस्थित करें जैसे कि 'गिरफ्तार [जे]' मैं 'हो जाता है अगर' गिरफ्तार [i] '' जी 'है

कोड

C ++ कोड एक सरणी को पुनर्व्यवस्थित करने के लिए ऐसा है कि 'गिरफ्तार [j]' हो जाता है 'i' अगर 'arr [i]' है '' ''

#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

जावा कोड एक सरणी को पुनर्व्यवस्थित करने के लिए ऐसा है कि 'गिरफ्तार [जे]' मैं 'बन जाता है अगर' गिरफ्तार [i] 'जी'

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

जटिलता विश्लेषण

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। भले ही हम सरणी के तत्वों पर दो बार ट्रेस किए। तो, यह अभी भी केवल रैखिक समय जटिलता के रूप में गिना जाता है।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। चूंकि हमने प्रत्येक तत्व से संबंधित कुछ भी संग्रहीत नहीं किया है और केवल निरंतर स्थान ले रहा है। इसलिए, एल्गोरिथ्म के लिए अंतरिक्ष जटिलता निरंतर है।