એરે ફરીથી ગોઠવો આવા કે એરર [i] i બરાબર છે


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એક્સેન્ચર એડોબ એમેઝોન કટ્ટરતા ફોરકાઇટ્સ ઝોહો
અરે હેશ

"એરેને ફરીથી ગોઠવો જેમ કે એરે [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 ની રેન્જની અંદરની સંખ્યા ધરાવશે. કેટલાક સંખ્યાઓ ગુમ થઈ શકે છે શ્રેણી માંથી. અમે તે બધા તત્વોને બદલવાનું કહ્યું છે જ્યાં એરે [i] 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] ની વેલ્યુ વેલ્યુ માટે એક એરે લીધી છે. અને છેલ્લે પ્રિન્ટ પર એરેના તે વેલ્યુ.

એરેની ફરીથી ગોઠવો જેમ કે એરે [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) સતત જગ્યા લે છે પરંતુ ઇનપુટ એરેમાં સંગ્રહિત હોવાથી. અમને મળે છે ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.