Массивті 'arr [j]' 'i' болатындай етіп реттеңіз, егер 'arr [i]' 'j' 'болса


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Дели Кулиза Нагарро опера Times Интернет Yatra
Array

Проблемалық мәлімдеме

«Массивті 'arr [j]' 'i' болатындай етіп реттеңіз, егер 'arr [i]' 'j' '' болса, онда сізде «N» бүтін сандардан тұратын өлшемді жиым. Массивтегі сандар 0-ден n-1 аралығында. Есептер жиыны [i] = j жиымы [j] = i болатындай етіп массивті қайта құруды сұрайды.

мысал

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

Түсіндіру

arr [0] = 1 arr [1] = 0 болып өзгертілді

arr [1] = 3 arr [3] = 1 болып өзгертілді

arr [2] = 5 arr [5] = 2 болып өзгертілді

arr [3] = 2 arr [2] = 3 болып өзгертілді

arr [4] = 0 arr [0] = 4 болып өзгертілді

arr [5] = 4 arr [4] = 5 болып өзгертілді

сондықтан басылған кезде ⇒

arr [0] ⇒ arr [1] ⇒ arr [2] ⇒ arr [3] ⇒ arr [4] ⇒ arr [5]

4 0 3 1 5 2

'Arr [j]' 'i' болатын массивті қайта реттеу алгоритмі, егер 'arr [i]' 'j' болса

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 жиымының орнын өзгертеміз. Массивтегі элементтер arr [j] = i болатындай болады, егер ол [i] = j болса. Осылайша, егер бізде ith күйінде j мәні бар болса, онда бұл мәнді жиымның j жағдайына ауыстырыңыз. Сонымен қатар, біз 0-ден n-1 аралығында массив элементтерін бердік. Сонымен, сан массивтің ұзындығынан аспауы керек. Біз массивті айналып өткенде пайдалы болуы мүмкін, біз кез-келген сан мәнін индекс ретінде қабылдап, оған бірнеше амалдар жасай аламыз.

Біз кейбір амалдарды массивтің өзінде орындаймыз. Біз массивтің әр элементін таңдап аламыз модуль arr [i]% n, мұндағы n - массивтің ұзындығы. Енді, сандар 0-ден n-1 аралығында болатынын бұрын айтқанымыздай. N-мен кез-келген санның модулін білгенде. Ол жиым индексінен үлкен саннан аспайды, өйткені [i]% n arr модулі қайтадан жиым индексі ретінде қарастырылады. Содан кейін біз оны i * n көбейтуінде сақтаймыз. Модульдің әрбір мәнін массивтің индексі ретінде жаңартыңыз және оны өзіңізбен қосыңыз.

Біз мұны тек массивтегі мәндерді алу үшін оларды сақтау және жаңарту үшін жасаймыз. Біз оларды бөлуіміз керек. Егер сіз санды х-ге көбейтіп, х-ге бөлсеңіз, сан сол күйінде бейтарап болады. [I] arr-ны бірдей arr [i] -ді n-ге бөлу арқылы жаңартып, arr [i] -ге сақтаңыз. Осылайша, біз қажетті нәтижеге қол жеткіземіз. Массивті 'arr [j]' егер 'arr [i]' 'j' болған жағдайда 'i' 'болатындай етіп өзгерту керек.

Массивті 'arr [j]' 'i' болатындай етіп реттеңіз, егер 'arr [i]' 'j' 'болса

код

Массивті қайта реттеуге арналған C ++ коды, егер 'arr [i]' 'j' болса, 'arr [j]' 'мен' 'болады.

#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

Массивті қайта реттеуге арналған Java коды, егер 'arr [i]' 'j' болса, 'arr [j]' '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

Күрделілікті талдау

Уақыттың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны. Біз массив элементтерін екі рет айналып өттік. Сонымен, бұл тек уақыттың сызықтық күрделілігі ретінде саналады.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны. Әр элементке қатысты ештеңе сақтамағандықтан және тек тұрақты кеңістікті алып отырғандықтан. Сонымен, алгоритм үшін кеңістіктің күрделілігі тұрақты.