Преуредување на низата така што 'arr [j]' станува 'i' ако 'arr [i]' е 'j'


Ниво на тешкотија Лесно
Често прашувано во Амазон Деливерија Кулиза Нагаро Опера Тајмс Интернет Yatra
Низа

Изјава за проблем

Проблемот „Преуредување низа така што„ ar [j] “станува„ i “ако„ arr [i] “е„ j ““ наведува дека имате „Н“ големина на низа што содржи цели броеви. Броевите во низата се во опсег од 0 до n-1. Со изјавата за проблем се бара преуредување на низата на таков начин што низата [i] = j станува arr [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. rearе ги преуредиме броевите од низата. Така што елементите во низата стануваат такви што arr [j] = i ако е arr [i] = j. Така, ова значи ако имаме одредена вредност во ith позиција како j, тогаш смени ја таа вредност во j-та позиција на низата. Исто така, дадовме елементи на низа во опсег од 0 до n-1. Значи, бројот не може да ја надмине должината на низата. Значи, може да биде од корист кога ќе ја поминеме низата, можеме да земеме каква било бројна вредност како индекс и да извршиме некои операции на неа.

Затоа што ќе извршиме некои операции на самата низа. Willе го избереме секој елемент од низата и ќе го најдеме modulo од arr [i]% n, каде n е должината на низата. Сега, како што споменавме порано, броевите се во опсег од 0 до n-1. Значи, кога ќе го дознаеме модулот на кој било број со n. Тој нема да го надмине бројот поголем од индекс на низата, бидејќи модулот на arr [i]% n повторно ќе се третира како индекс на низа. И тогаш го чуваме во множење на i * n. Ажурирајте ја секоја вредност на модулот како индекс на низата и сумирајте ја со себе.

Ние само го правиме ова за да ги зачуваме и ажурираме вредностите во низата, ако ги земеме. Треба само да ги поделиме. Затоа што ако го множиш бројот со x и го поделиш со x, бројот ќе стане неутрален каков што е. Ажурирајте го arr [i] со делење на истиот ar [i] со n и зачувајте го на arr [i]. На овој начин, ќе го добиеме посакуваниот резултат. Тоа е начинот на преуредување на низата така што 'arr [j]' станува 'i' ако 'arr [i]' е 'j'.

Преуредување на низата така што 'arr [j]' станува 'i' ако 'arr [i]' е 'j'

Код

C ++ код за преуредување на низата така што 'arr [j]' станува 'i' ако 'arr [i]' е '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 [j]' станува 'i' ако 'arr [i]' е 'j'

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

Анализа на сложеност

Временска комплексност

Тој) каде „Н“ е бројот на елементи во низата. И покрај тоа што двапати ги прелистувавме елементите на низата. Значи, ова сè уште се смета само за линеарна сложеност во времето.

Комплексноста на просторот

Тој) каде „Н“ е бројот на елементи во низата. Бидејќи не сме зачувале ништо поврзано со секој елемент и зафаќаме само постојан простор. Значи, комплексноста на просторот за алгоритмот е постојана.