Переставьте массив так, чтобы arr [i] было равно i  


Сложный уровень Легко
Часто спрашивают в Accenture саман Амазонка Фанатики Фуркиты Zoho
массив Hash

Задача «Переупорядочить массив так, чтобы arr [i] = i» гласит, что вам дан массив целых чисел от 0 до n-1. Поскольку в массиве могут отсутствовать все элементы, то вместо них стоит -1. В формулировке задачи предлагается переупорядочить массив таким образом, если в массиве нет числа между диапазоном, пометьте его как -1 и переставьте элементы как arr [i] = i.

Пример  

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

Пояснение: Поскольку любой элемент отсутствует в диапазоне затем он был заменен на -1 и индекс массива заменяется самим числом.

Алгоритм переупорядочивания массива таким образом, чтобы arr [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. Несколько из числа могут отсутствовать из ассортимента. Мы попросили заменить все элементы, где arr [i] становится значением i. Если в массиве нет числа, мы должны заменить его на -1. Предположим, у нас есть диапазон от 0 до 4. В котором у нас есть только 2 и 3 в массиве, а остальные -1 как элементы, тогда мы должны поместить 2 и 3 в индекс как arr [2] = 2 и arr [3] = 3, а остальные места будут помечены как -1, если какое-либо из чисел не присутствует в диапазоне от 0 до 4.

Смотрите также
Найти пару с наибольшим произведением в массиве

Мы дали массив. Наша основная идея - поменять местами элементы массива для решения задачи «Переупорядочить массив так, чтобы arr [i] = i». Мы собираемся пройти по массиву от 0 до n-1 и проверить каждое значение «i». Если arr [i] больше 0, чтобы избежать отрицательные числа. Там также применяется условие, чтобы цикл не продолжался бесконечно, поскольку мы увеличиваем значение 'i' в части else, поэтому мы также проверяем, что arr [i] также не должно быть равным «i». Так что он может пропустить и двигаться дальше и проверить дальнейшие значения.

Нам просто нужно поменять местами те значения, которые больше 0 и не равны i. Кроме того, мы меняем местами внутри массива с помощью одного цикла в пределах диапазона, поэтому мы взяли массив значений arr [i] для обмена. И, наконец, распечатайте эти значения массива.

Перегруппируйте массив так, чтобы arr [i] = i

Реализация  

Программа на C ++ для переупорядочения массива таким образом, чтобы arr [i] было равно 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

Программа на Java для переупорядочивания массива таким образом, чтобы arr [i] было равно 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]

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

Сложность времени

Поскольку мы просто обходили массив, мы достигли линейной временной сложности. НА) в котором "N", - количество элементов в массиве для задачи «Переупорядочить массив так, чтобы arr [i] = i».

Смотрите также
Пиковый индекс в горном массиве

Космическая сложность

Сам алгоритм занимает постоянное пространство O (1), но поскольку входные данные хранятся в массиве. Мы получили НА) в котором "N", это количество элементов в массиве.