ഒരു അറേ പുന range ക്രമീകരിക്കുക അത്തരം [i] എനിക്ക് തുല്യമാണ്


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഓട്ടോമോട്ടീവ് അഡോബി ആമസോൺ ഫനാറ്റിക്സ് ഫോർകൈറ്റുകൾ Zoho
അറേ ഹാഷ്

“Ar [i] = i” എന്ന ഒരു ശ്രേണി പുന range ക്രമീകരിക്കുക, നിങ്ങൾക്ക് 0 മുതൽ n-1 വരെയുള്ള പൂർണ്ണസംഖ്യകളുടെ ഒരു നിര നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. എല്ലാ ഘടകങ്ങളും അറേയിൽ‌ ഇല്ലായിരിക്കാം എന്നതിനാൽ‌, അവയുടെ സ്ഥാനത്ത് -1 ഉണ്ട്. ശ്രേണികൾക്കിടയിലുള്ള ഒരു സംഖ്യ ഒരു അറേയിൽ ഇല്ലെങ്കിൽ അറേ പുന range ക്രമീകരിക്കാൻ പ്രശ്‌ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു, തുടർന്ന് അത് -1 എന്ന് അടയാളപ്പെടുത്തി ഘടകങ്ങളെ arr [i] = i എന്ന് പുന range ക്രമീകരിക്കുക.

ഉദാഹരണം

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

വിശദീകരണം: ഏതെങ്കിലും മുതൽ ഘടകം പരിധിക്കുള്ളിൽ ഇല്ല അതിനുശേഷം, അത് -1 ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കുകയും അറേ സൂചികയെ സംഖ്യ ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കുകയും ചെയ്യുന്നു.

ഒരു ശ്രേണി പുന ar ക്രമീകരിക്കുന്നതിനുള്ള അൽ‌ഗോരിതം അത്തരത്തിലുള്ള [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. 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” ന്റെ ഓരോ മൂല്യവും പരിശോധിക്കാൻ പോകുന്നു. Ar [i] 0 നേക്കാൾ വലുതാണെങ്കിൽ നമുക്ക് ഒഴിവാക്കാം നെഗറ്റീവ് സംഖ്യകൾ. മറ്റൊരു ഭാഗത്ത് 'i' ന്റെ മൂല്യം വർദ്ധിപ്പിക്കുന്നതിനാൽ ലൂപ്പ് അനന്തമായി പോകാതിരിക്കാൻ ഒരു നിബന്ധനയും അവിടെ പ്രയോഗിക്കുന്നു, അതിനാൽ ar [i] “i” ന് തുല്യമാകരുത് എന്നും ഞങ്ങൾ പരിശോധിക്കുന്നു. അതുവഴി ഒഴിവാക്കാനും കൂടുതൽ നീങ്ങാനും കൂടുതൽ മൂല്യങ്ങൾ പരിശോധിക്കാനും കഴിയും.

0 ന് തുല്യവും i ന് തുല്യമല്ലാത്തതുമായ മൂല്യങ്ങൾ‌ ഞങ്ങൾ‌ സ്വാപ്പ് ചെയ്യേണ്ടതുണ്ട്. കൂടാതെ, ഞങ്ങൾ ഒരു പരിധിക്കുള്ളിൽ ഒരൊറ്റ ലൂപ്പ് ഉപയോഗിച്ച് അറേയ്ക്കുള്ളിൽ സ്വാപ്പ് ചെയ്യുന്നു, അതിനാലാണ് സ്വാപ്പ് ചെയ്യുന്നതിന് ഞങ്ങൾ അറ [i] മൂല്യങ്ങളുടെ ഒരു നിര എടുത്തത്. അവസാനം അറേയുടെ ആ മൂല്യങ്ങൾ അച്ചടിക്കുക.

Arr [i] = i പോലുള്ള ഒരു ശ്രേണി പുന range ക്രമീകരിക്കുക

നടപ്പിലാക്കൽ

ഒരു അറേ പുന range ക്രമീകരിക്കുന്നതിനുള്ള സി ++ പ്രോഗ്രാം അത്തരം [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

ഒരു അറേ പുന range ക്രമീകരിക്കുന്നതിനുള്ള ജാവ പ്രോഗ്രാം അത്തരത്തിലുള്ള [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” പ്രശ്‌നമുള്ള ഒരു ശ്രേണി പുന range ക്രമീകരിക്കുക എന്നതിനായുള്ള അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

ബഹിരാകാശ സങ്കീർണ്ണത

അൽ‌ഗോരിതം തന്നെ O (1) സ്ഥിരമായ ഇടം എടുക്കുന്നു, പക്ഷേ ഇൻ‌പുട്ട് ഒരു അറേയിൽ‌ സംഭരിച്ചിരിക്കുന്നതിനാൽ‌. ഞങ്ങൾക്ക് ലഭിക്കുന്നു O (N) എവിടെ "N" അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.