Пренаредете масив така, че „arr [j]“ да стане „i“, ако „arr [i]“ е „j“  


Ниво на трудност Лесно
Често задавани в Амазонка Делхейвъри Кулиза Нагаро опера Times Интернет Yatra
Array

Декларация за проблема  

Проблемът „Пренареждане на масив, така че„ arr [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. Ще пренаредим числата pf масив. Така че елементите в масива да станат такива, че arr [j] = i, ако е arr [i] = j. По този начин това означава, че ако имаме някаква стойност в i-та позиция като j, тогава променете тази стойност на j-та позиция на масив. Също така, ние сме дали елементи на масив в диапазона от 0 до n-1. Така че числото не може да надвишава дължината на масив. Така че може да бъде от полза, когато прекосим масива, можем да вземем произволна числова стойност като индекс и да извършим някои операции върху него.

Вижте също
Начини за декодиране

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

Ние просто правим това, за да съхраняваме и актуализираме стойностите в масива, ако ще ги извлечем. Просто трябва да ги разделим. Защото ако умножите числото с x и разделите с x, числото ще стане неутрално, както е. Актуализирайте arr [i], като разделите същия arr [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

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

Сложност във времето

О (п) където "н" е броят на елементите в масива. Въпреки че два пъти прекосихме елементите на масива. Така че, това все още се брои като линейна времева сложност.

Вижте също
Бройте поднизи с еднакви четни и нечетни елементи

Сложност на пространството

О (п) където "н" е броят на елементите в масива. Тъй като не сме съхранили нищо свързано с всеки елемент и заемаме само постоянно пространство. Така че сложността на пространството за алгоритъма е постоянна.