Рубрики

Переставьте массив так, чтобы arr [i] стал arr [arr [i]] с O (1) дополнительным пробелом

Дан массив arr [] размера n, где каждый элемент находится в диапазоне от 0 до n-1 . Переставьте данный массив так, чтобы arr [i] стал arr [arr [i]] . Это должно быть сделано с O (1) дополнительным пробелом.

Примеры:

Input: arr[]  = {3, 2, 0, 1}
Output: arr[] = {1, 0, 3, 2}

Input: arr[] = {4, 0, 2, 1, 3}
Output: arr[] = {3, 4, 2, 0, 1}

Input: arr[] = {0, 1, 2, 3}
Output: arr[] = {0, 1, 2, 3}

Если лишнее условие пространства удаляется, вопрос становится очень легким. Основная часть вопроса — сделать это без лишних пробелов.

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Кредит на следующее решение переходит к Ганеш Рам Сундарам . Ниже приведены шаги.

1) Увеличьте каждый элемент массива arr [i] на (arr [arr [i]]% n) * n.
2) Разделите каждый элемент на n.

Let us understand the above steps by an example array {3, 2, 0, 1}
In first step, every value is incremented by (arr[arr[i]] % n)*n
After first step array becomes {7, 2, 12, 9}. 
The important thing is, after the increment operation
of first step, every element holds both old values and new values. 
Old value can be obtained by arr[i]%n and new value can be obtained
by arr[i]/n.

In second step, all elements are updated to new or output values 
by doing arr[i] = arr[i]/n.
After second step, array becomes {1, 0, 3, 2}

Ниже приводится реализация вышеуказанного подхода.

C ++

#include <iostream>

using namespace std;

  
// Функция для перестановки массива на месте, чтобы arr [i]
// становится arr [arr [i]].

void rearrange(int arr[], int n)

{

    // Первый шаг: увеличить все значения на (arr [arr [i]]% n) * n

    for (int i=0; i < n; i++)

        arr[i] += (arr[arr[i]]%n)*n;

  

    // Второй шаг: разделить все значения на n

    for (int i=0; i<n; i++)

        arr[i] /= n;

}

  
// Вспомогательная функция для печати массива размера n

void printArr(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

    cout << endl;

}

  

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    int arr[] = {3, 2, 0, 1};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    cout << "Given array is \n";

    printArr(arr, n);

  

    rearrange(arr, n);

  

    cout << "Modified array is \n";

    printArr(arr, n);

    return 0;

}

Джава

class Rearrange 

{

    // Функция для перестановки массива на месте, чтобы arr [i]

    // становится arr [arr [i]].

    void rearrange(int arr[], int n) 

    {

        // Первый шаг: увеличить все значения на (arr [arr [i]]% n) * n

        for (int i = 0; i < n; i++)

            arr[i] += (arr[arr[i]] % n) * n;

  

        // Второй шаг: разделить все значения на n

        for (int i = 0; i < n; i++)

            arr[i] /= n;

    }

  

    // Вспомогательная функция для печати массива размера n

    void printArr(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) 

    {

        Rearrange rearrange = new Rearrange();

        int arr[] = {3, 2, 0, 1};

        int n = arr.length;

  

        System.out.println("Given Array is :");

        rearrange.printArr(arr, n);

  

        rearrange.rearrange(arr, n);

  

        System.out.println("Modified Array is :");

        rearrange.printArr(arr, n);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Python3 программа для перестановки
# массив, так что arr [i] становится
# arr [arr [i]]

  
# Функция переставить
# массив на месте, так что arr [i]
# становится arr [arr [i]].

def rearrange(arr, n):

  

    # Первый шаг: увеличить все значения

    # by (arr [arr [i]]% n) * n

    for i in range(0, n):

        arr[i] += (arr[arr[i]] % n) * n

  

    # Второй шаг: разделите все значения

    # по n

    for i in range(0, n):

        arr[i] = int(arr[i] / n)

  
# Утилита для печати
# массив размером n

def printArr(arr, n):

  

    for i in range(0, n):

        print (arr[i], end =" ")

    print ("")

  
# Драйверная программа

arr = [3, 2, 0, 1]

n = len(arr)

  

print ("Given array is")

printArr(arr, n)

  
rearrange(arr, n);

print ("Modified array is")

printArr(arr, n)

  
# Этот код предоставлен shreyanshi_arun

C #

// C # Программа для перестановки массива
// чтобы arr [i] стал arr [arr [i]]
// с O (1) дополнительным пробелом

using System;

  

class Rearrange

{

      

    // Функция перестановки

    // массив на месте, так что arr [i]

    // становится arr [arr [i]].

    void rearrange(int []arr, int n) 

    {

          

        // Первый шаг: увеличить все значения

        // by (arr [arr [i]]% n) * n

        for (int i = 0; i < n; i++)

            arr[i] += (arr[arr[i]] % n) * n;

  

        // Второй шаг: разделить все значения на n

        for (int i = 0; i < n; i++)

            arr[i] /= n;

    }

  

    // Функция полезности для

    // выводим массив размером n

    void printArr(int []arr, int n) 

    {

        for (int i = 0; i < n; i++)

            Console.Write(arr[i] + " ");

        Console.WriteLine("");

    }

  

    // Код драйвера

    public static void Main() 

    {

        Rearrange rearrange = new Rearrange();

        int []arr = {3, 2, 0, 1};

        int n = arr.Length;

  

        Console.Write("Given Array is :");

        rearrange.printArr(arr, n);

  

        rearrange.rearrange(arr, n);

  

        Console.Write("Modified Array is :");

        rearrange.printArr(arr, n);

    }

}

  
// Этот код предоставлен Нитином Митталом.

PHP

<?php 
// Функция для перестановки массива
// на месте, так что arr [i] становится arr [arr [i]].

function rearrange(&$arr, $n)

{

    // Первый шаг: увеличить все значения

    // by (arr [arr [i]]% n) * n

    for ($i = 0; $i < $n; $i++)

        $arr[$i] += ($arr[$arr[$i]] % $n) * $n;

  

    // Второй шаг: разделить все значения на n

    for ($i = 0; $i < $n; $i++)

        $arr[$i] = intval($arr[$i] / $n);

}

  
// Утилита для печати
// массив размером n

function printArr(&$arr, $n)

{

    for ($i = 0; $i < $n; $i++)

        echo $arr[$i] ." ";

    echo "\n";

}

  

  
// Код драйвера

$arr = array(3, 2, 0, 1);

$n = sizeof($arr);

  

echo "Given array is \n";

printArr($arr, $n);

  

rearrange($arr, $n);

  

echo "Modified array is \n";

printArr($arr, $n);

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

Given array is
3 2 0 1
Modified array is
1 0 3 2

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Проблема с вышеупомянутым решением, это может вызвать переполнение.

Пожалуйста, смотрите ниже сообщение для лучшего решения:
Переставьте массив так, чтобы arr [j] стал i, если arr [i] равен j

Эта статья предоставлена Химаншу Гупта . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Переставьте массив так, чтобы arr [i] стал arr [arr [i]] с O (1) дополнительным пробелом

0.00 (0%) 0 votes