අරාව නැවත සකස් කරන්න එවැනි [i] i ට සමාන වේ


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇක්සෙන්චර් ඇෙබෝ ඇමේසන් උන්මත්තකයෝ ෆෝකයිට් Zoho
අරා හැෂ්

“Ar [i] = i” වැනි අරාව නැවත සකස් කරන්න ඔබට 0 සිට n-1 දක්වා පූර්ණ සංඛ්‍යා සමූහයක් ලබා දී ඇති බව සඳහන් වේ. සියලු මූලද්‍රව්‍යයන් අරාවෙහි නොපවතින බැවින් ඒවා වෙනුවට -1 පවතී. අරාව තුළ පරාසය අතර සංඛ්‍යාවක් නොමැති නම් අරාව නැවත සකස් කිරීමට ගැටළු ප්‍රකාශය ඉල්ලා සිටින අතර එය -1 ලෙස සලකුණු කර මූලද්‍රව්‍ය ar [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] සමාන වේ

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 පරාසය තුළ ඇති සංඛ්‍යා අඩංගු වේ. සමහරක් අංක අතුරුදහන් විය හැකිය පරාසයෙන්. Ar [i] අගය බවට පත්වන සියලුම මූලද්‍රව්‍ය ප්‍රතිස්ථාපනය කිරීමට අපි ඉල්ලා සිටිමු. අරාව තුළ අංකයක් නොමැති නම් අපි එය -1 සමඟ ආදේශ කළ යුතුය. අපට 0 සිට 4 දක්වා පරාසයක් ඇතැයි සිතමු. එහි අපට ඇත්තේ 2 සහ 3 ක් පමණි. එහි ඉතිරි කොටස -1 ලෙස මූලද්‍රව්‍ය ලෙස පවතී, එවිට අපට දර්ශකයේ 2 සහ 3 ස්ථානගත කළ යුතුය [2] = 2 සහ arr [3] = 3 සහ 1 සිට 0 දක්වා පරාසයක් තුළ කිසියම් සංඛ්‍යාවක් නොමැති නම් ඉතිරි ස්ථාන -4 ලෙස සලකුණු කෙරේ.

අපි අරාවක් දීලා තියෙනවා. අපගේ ප්‍රධාන අදහස වන්නේ “අරාව [i] = i” ගැටළුව විසඳීම සඳහා අරාවෙහි අංග මාරු කිරීමයි. අපි අරාව 0 සිට n-1 දක්වා ගමන් කර “i” හි එක් එක් අගය පරීක්ෂා කරන්නෙමු. Arr [i] 0 ට ​​වඩා වැඩි නම් අපට එය වළක්වා ගත හැකිය negative ණ සංඛ්‍යා. අපි වෙනත් කොටසක 'i' හි අගය වැඩි කරන බැවින්, ලූපය අසීමිත නොවන පරිදි එහි යෙදෙන කොන්දේසියක් ද ඇත, එබැවින් අපි ද පරීක්ෂා කර බලමු [i] ද "i" ට සමාන නොවිය යුතු බව. එමඟින් එය මඟ හැර ඉදිරියට යා හැකි අතර තවත් අගයන් තිබේදැයි පරීක්ෂා කරන්න.

අපට අවශ්‍ය වන්නේ 0 ට වඩා වැඩි හා i ට සමාන නොවන අගයන් මාරු කිරීමයි. එසේම, අපි අරාව තුළ තනි පුඩුවක් සමඟ, පරාසයක් තුළ හුවමාරු වෙමින් සිටිමු, ඒ නිසා අපි හුවමාරු කර ගැනීම සඳහා අර්‍ [i] අගයන් රාශියක් ගෙන ඇත. අවසානයේදී අරාවේ අගයන් මුද්‍රණය කරන්න.

Ar [i] = i වැනි අරාවක් නැවත සකස් කරන්න

ක්රියාත්මක කිරීම

අරාව නැවත සකස් කිරීම සඳහා C ++ වැඩසටහන අර්‍ [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] සමාන වේ

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” ගැටළුවයි.

අභ්‍යවකාශ සංකීර්ණතාව

ඇල්ගොරිතමයටම O (1) නියත ඉඩක් ගතවන නමුත් ආදානය අරාව තුළ ගබඩා කර ඇති බැවින්. අපිට ලැබෙනවා මත) එහිදී “එන්” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.