Dadas dos arrays de enteros del mismo tamaño, «arr[]» e «index[]», reordene los elementos en «arr[]» de acuerdo con la array de índice dada. No está permitido dar la longitud de la array arr.
Ejemplo:
Input: arr[] = [10, 11, 12];
index[] = [1, 0, 2];
Output: arr[] = [11, 10, 12]
index[] = [0, 1, 2]
Input: arr[] = [50, 40, 70, 60, 90]
index[] = [3, 0, 4, 1, 2]
Output: arr[] = [40, 60, 90, 50, 70]
index[] = [0, 1, 2, 3, 4]
Complejidad temporal esperada O(n) y espacio auxiliar O(1)
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Una solución simple es usar una array auxiliar temp[] del mismo tamaño que las arrays dadas. Recorra la array dada y coloque todos los elementos en su lugar correcto en temp[] usando index[]. Finalmente, copie temp[] en arr[] y configure todos los valores de index[i] como i.
C++
// C++ program to sort an array according to given
// indexes
#include<iostream>
using namespace std;
// Function to reorder elements of arr[] according
// to index[]
void reorder(int arr[], int index[], int n)
{
int temp[n];
// arr[i] should be present at index[i] index
for (int i=0; i<n; i++)
temp[index[i]] = arr[i];
// Copy temp[] to arr[]
for (int i=0; i<n; i++)
{
arr[i] = temp[i];
index[i] = i;
}
}
// Driver program
int main()
{
int arr[] = {50, 40, 70, 60, 90};
int index[] = {3, 0, 4, 1, 2};
int n = sizeof(arr)/sizeof(arr[0]);
reorder(arr, index, n);
cout << "Reordered array is: \n";
for (int i=0; i<n; i++)
cout << arr[i] << " ";
cout << "\nModified Index array is: \n";
for (int i=0; i<n; i++)
cout << index[i] << " ";
return 0;
}
Java
//Java to find positions of zeroes flipping which
// produces maximum number of consecutive 1's
import java.util.Arrays;
class Test
{
static int arr[] = new int[]{50, 40, 70, 60, 90};
static int index[] = new int[]{3, 0, 4, 1, 2};
// Method to reorder elements of arr[] according
// to index[]
static void reorder()
{
int temp[] = new int[arr.length];
// arr[i] should be present at index[i] index
for (int i=0; i<arr.length; i++)
temp[index[i]] = arr[i];
// Copy temp[] to arr[]
for (int i=0; i<arr.length; i++)
{
arr[i] = temp[i];
index[i] = i;
}
}
// Driver method to test the above function
public static void main(String[] args)
{
reorder();
System.out.println("Reordered array is: ");
System.out.println(Arrays.toString(arr));
System.out.println("Modified Index array is:");
System.out.println(Arrays.toString(index));
}
}
Python3
# Python3 program to sort
# an array according to given
# indexes
# Function to reorder
# elements of arr[] according
# to index[]
def reorder(arr,index, n):
temp = [0] * n;
# arr[i] should be
# present at index[i] index
for i in range(0,n):
temp[index[i]] = arr[i]
# Copy temp[] to arr[]
for i in range(0,n):
arr[i] = temp[i]
index[i] = i
# Driver program
arr = [50, 40, 70, 60, 90]
index = [3, 0, 4, 1, 2]
n = len(arr)
reorder(arr, index, n)
print("Reordered array is:")
for i in range(0,n):
print(arr[i],end = " ")
print("\nModified Index array is:")
for i in range(0,n):
print(index[i],end = " ")
# This code is contributed by
# Smitha Dinesh Semwal
C#
// C# to find positions of zeroes flipping which
// produces maximum number of consecutive 1's
using System;
public class Test{
static int []arr = new int[]{50, 40, 70, 60, 90};
static int []index = new int[]{3, 0, 4, 1, 2};
// Method to reorder elements of arr[] according
// to index[]
static void reorder()
{
int []temp = new int[arr.Length];
// arr[i] should be present at index[i] index
for (int i=0; i<arr.Length; i++)
temp[index[i]] = arr[i];
// Copy temp[] to arr[]
for (int i=0; i<arr.Length; i++)
{
arr[i] = temp[i];
index[i] = i;
}
}
// Driver method to test the above function
public static void Main()
{
reorder();
Console.WriteLine("Reordered array is: ");
Console.WriteLine(string.Join(",", arr));
Console.WriteLine("Modified Index array is:");
Console.WriteLine(string.Join(",", index));
}
}
/*This code is contributed by 29AjayKumar*/
PHP
<?php
// PHP program to sort an array
// according to given indexes
// Function to reorder elements
// of arr[] according to index[]
function reorder($arr, $index, $n)
{
// $temp[$n];
// arr[i] should be present
// at index[i] index
for ($i = 0; $i < $n; $i++)
{
$temp[$index[$i]] = $arr[$i];
}
// Copy temp[] to arr[]
for ($i = 0; $i < $n; $i++)
{
$arr[$i] = $temp[$i];
$index[$i] = $i;
}
echo "Reordered array is: \n";
for ($i = 0; $i < $n; $i++)
{
echo $arr[$i] . " ";
}
echo "\nModified Index array is: \n";
for ($i = 0; $i < $n; $i++)
{
echo $index[$i] . " ";
}
}
// Driver Code
$arr = array(50, 40, 70, 60, 90);
$index = array(3, 0, 4, 1, 2);
$n = sizeof($arr);
reorder($arr, $index, $n);
// This code is contributed
// by Abby_akku
?>
Javascript
<script>
// JavaScript program to sort an array according to given
// indexes
// Function to reorder elements of arr[] according
// to index[]
function reorder(arr, index, n) {
var temp = [...Array(n)];
// arr[i] should be present at index[i] index
for (var i = 0; i < n; i++) temp[index[i]] = arr[i];
// Copy temp[] to arr[]
for (var i = 0; i < n; i++) {
arr[i] = temp[i];
index[i] = i;
}
}
// Driver program
var arr = [50, 40, 70, 60, 90];
var index = [3, 0, 4, 1, 2];
var n = arr.length;
reorder(arr, index, n);
document.write("Reordered array is: ");
document.write("<br>");
for (var i = 0; i < n; i++) document.write(arr[i] + " ");
document.write("<br>");
document.write("Modified Index array is: ");
document.write("<br>");
for (var i = 0; i < n; i++) document.write(index[i] + " ");
// This code is contributed by rdtank.
</script>
Producción:
Reordered array is: 40 60 90 50 70 Modified Index array is: 0 1 2 3 4
Gracias a gccode por sugerir la solución anterior.
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Podemos resolverlo Sin Auxiliary Array . A continuación se muestra el algoritmo.
1) Do following for every element arr[i]
a) While index[i] is not equal to i
(i) Store array and index values of the target (or
correct) position where arr[i] should be placed.
The correct position for arr[i] is index[i]
(ii) Place arr[i] at its correct position. Also
update index value of correct position.
(iii) Copy old values of correct position (Stored in
step (i)) to arr[i] and index[i] as the while
loop continues for i.
A continuación se muestra la implementación del algoritmo anterior.
C++
// A O(n) time and O(1) extra space C++ program to
// sort an array according to given indexes
#include<iostream>
using namespace std;
// Function to reorder elements of arr[] according
// to index[]
void reorder(int arr[], int index[], int n)
{
// Fix all elements one by one
for (int i=0; i<n; i++)
{
// While index[i] and arr[i] are not fixed
while (index[i] != i)
{
// Store values of the target (or correct)
// position before placing arr[i] there
int oldTargetI = index[index[i]];
char oldTargetE = arr[index[i]];
// Place arr[i] at its target (or correct)
// position. Also copy corrected index for
// new position
arr[index[i]] = arr[i];
index[index[i]] = index[i];
// Copy old target values to arr[i] and
// index[i]
index[i] = oldTargetI;
arr[i] = oldTargetE;
}
}
}
// Driver program
int main()
{
int arr[] = {50, 40, 70, 60, 90};
int index[] = {3, 0, 4, 1, 2};
int n = sizeof(arr)/sizeof(arr[0]);
reorder(arr, index, n);
cout << "Reordered array is: \n";
for (int i=0; i<n; i++)
cout << arr[i] << " ";
cout << "\nModified Index array is: \n";
for (int i=0; i<n; i++)
cout << index[i] << " ";
return 0;
}
Java
//A O(n) time and O(1) extra space Java program to
//sort an array according to given indexes
import java.util.Arrays;
class Test
{
static int arr[] = new int[]{50, 40, 70, 60, 90};
static int index[] = new int[]{3, 0, 4, 1, 2};
// Method to reorder elements of arr[] according
// to index[]
static void reorder()
{
// Fix all elements one by one
for (int i=0; i<arr.length; i++)
{
// While index[i] and arr[i] are not fixed
while (index[i] != i)
{
// Store values of the target (or correct)
// position before placing arr[i] there
int oldTargetI = index[index[i]];
char oldTargetE = (char)arr[index[i]];
// Place arr[i] at its target (or correct)
// position. Also copy corrected index for
// new position
arr[index[i]] = arr[i];
index[index[i]] = index[i];
// Copy old target values to arr[i] and
// index[i]
index[i] = oldTargetI;
arr[i] = oldTargetE;
}
}
}
// Driver method to test the above function
public static void main(String[] args)
{
reorder();
System.out.println("Reordered array is: ");
System.out.println(Arrays.toString(arr));
System.out.println("Modified Index array is:");
System.out.println(Arrays.toString(index));
}
}
Python3
# A O(n) time and O(1) extra space Python3 program to
# sort an array according to given indexes
# Function to reorder elements of arr[] according
# to index[]
def reorder(arr, index, n):
# Fix all elements one by one
for i in range(0,n):
# While index[i] and arr[i] are not fixed
while (index[i] != i):
# Store values of the target (or correct)
# position before placing arr[i] there
oldTargetI = index[index[i]]
oldTargetE = arr[index[i]]
# Place arr[i] at its target (or correct)
# position. Also copy corrected index for
# new position
arr[index[i]] = arr[i]
index[index[i]] = index[i]
# Copy old target values to arr[i] and
# index[i]
index[i] = oldTargetI
arr[i] = oldTargetE
# Driver program
arr = [50, 40, 70, 60, 90]
index= [3, 0, 4, 1, 2]
n = len(arr)
reorder(arr, index, n)
print("Reordered array is:")
for i in range(0, n):
print(arr[i],end=" ")
print("\nModified Index array is:")
for i in range(0, n):
print(index[i] ,end=" ")
# This code is contributed by
# Smitha Dinesh Semwal
C#
//A O(n) time and O(1) extra space C# program to
//sort an array according to given indexes
using System;
public class Test
{
static int []arr = new int[]{50, 40, 70, 60, 90};
static int []index = new int[]{3, 0, 4, 1, 2};
// Method to reorder elements of arr[] according
// to index[]
static void reorder()
{
// Fix all elements one by one
for (int i=0; i<arr.Length; i++)
{
// While index[i] and arr[i] are not fixed
while (index[i] != i)
{
// Store values of the target (or correct)
// position before placing arr[i] there
int oldTargetI = index[index[i]];
char oldTargetE = (char)arr[index[i]];
// Place arr[i] at its target (or correct)
// position. Also copy corrected index for
// new position
arr[index[i]] = arr[i];
index[index[i]] = index[i];
// Copy old target values to arr[i] and
// index[i]
index[i] = oldTargetI;
arr[i] = oldTargetE;
}
}
}
// Driver method to test the above function
public static void Main()
{
reorder();
Console.WriteLine("Reordered array is: ");
Console.WriteLine(String.Join(" ",arr));
Console.WriteLine("Modified Index array is:");
Console.WriteLine(String.Join(" ",index));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// A O(n) time and O(1) extra space JavaScript program to
// sort an array according to given indexes
// Function to reorder elements of arr[] according
// to index[]
function reorder(arr, index, n)
{
// Fix all elements one by one
for (let i=0; i<n; i++)
{
// While index[i] and arr[i] are not fixed
while (index[i] != i)
{
// Store values of the target (or correct)
// position before placing arr[i] there
let oldTargetI = index[index[i]];
let oldTargetE = arr[index[i]];
// Place arr[i] at its target (or correct)
// position. Also copy corrected index for
// new position
arr[index[i]] = arr[i];
index[index[i]] = index[i];
// Copy old target values to arr[i] and
// index[i]
index[i] = oldTargetI;
arr[i] = oldTargetE;
}
}
}
// Driver program
let arr = [50, 40, 70, 60, 90];
let index = [3, 0, 4, 1, 2];
let n = arr.length;
reorder(arr, index, n);
document.write("Reordered array is: <br>");
for (let i=0; i<n; i++)
document.write(arr[i] + " ");
document.write("<br>Modified Index array is: <br>");
for (let i=0; i<n; i++)
document.write(index[i] + " ");
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
Reordered array is: 40 60 90 50 70 Modified Index array is: 0 1 2 3 4
Gracias a shyamala_lokre por sugerir la solución anterior.
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(1)
Otro método sin usar una array auxiliar es ordenar las arrays.
Ordene la array de índice y personalice la ordenación para intercambiar los datos de arr[] siempre que intercambie los datos de index[].
C++
//C++ code to reorder an array according to given indices
#include <bits/stdc++.h>
using namespace std;
int heapSize;
void swap ( int &a, int &b ) {
int temp = a;
a = b;
b = temp;
}
void heapify( int arr[], int index[], int i )
{
int largest = i;
// left child in 0 based indexing
int left = 2 * i + 1;
// right child in 1 based indexing
int right = 2 * i + 2;
// find largest index from root, left and right child
if( left < heapSize && index[left] > index[largest] )
{
largest = left;
}
if( right < heapSize && index[right] > index[largest] )
{
largest = right;
}
if ( largest != i ) {
//swap arr whenever index is swapped
swap(arr[largest], arr[i]);
swap(index[largest], index[i]);
heapify(arr, index, largest);
}
}
void heapSort( int arr[], int index[], int n ) {
// Build heap
for ( int i = ( n - 1 ) / 2 ; i >= 0 ; i-- ) {
heapify(arr, index, i);
}
// Swap the largest element of index(first element)
// with the last element
for ( int i = n - 1 ; i > 0 ; i-- ) {
swap(index[0], index[i]);
//swap arr whenever index is swapped
swap(arr[0], arr[i]);
heapSize--;
heapify(arr, index, 0);
}
}
// Driver Code
int main() {
int arr[] = {50, 40, 70, 60, 90};
int index[] = {3, 0, 4, 1, 2};
int n = sizeof(arr)/sizeof(arr[0]);
heapSize = n;
heapSort(arr, index, n);
cout << "Reordered array is: \n";
for ( int i = 0 ; i < n ; i++ )
cout << arr[i] << " ";
cout << "\nModified Index array is: \n";
for (int i=0; i<n; i++)
cout << index[i] << " ";
return 0;
}
Java
// Java code to reorder an array
// according to given indices
class GFG{
static int heapSize;
public static void heapify(int arr[],
int index[], int i)
{
int largest = i;
// left child in 0 based indexing
int left = 2 * i + 1;
// right child in 1 based indexing
int right = 2 * i + 2;
// Find largest index from root,
// left and right child
if (left < heapSize &&
index[left] > index[largest] )
{
largest = left;
}
if (right < heapSize &&
index[right] > index[largest] )
{
largest = right;
}
if (largest != i)
{
// swap arr whenever index is swapped
int temp = arr[largest];
arr[largest] = arr[i];
arr[i] = temp;
temp = index[largest];
index[largest] = index[i];
index[i] = temp;
heapify(arr, index, largest);
}
}
public static void heapSort(int arr[],
int index[], int n)
{
// Build heap
for(int i = (n - 1) / 2 ; i >= 0 ; i--)
{
heapify(arr, index, i);
}
// Swap the largest element of
// index(first element)
// with the last element
for(int i = n - 1 ; i > 0 ; i--)
{
int temp = index[0];
index[0] = index[i];
index[i] = temp;
// swap arr whenever index is swapped
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapSize--;
heapify(arr, index, 0);
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 50, 40, 70, 60, 90 };
int index[] = { 3, 0, 4, 1, 2 };
int n = arr.length;
heapSize = n;
heapSort(arr, index, n);
System.out.println("Reordered array is: ");
for(int i = 0 ; i < n ; i++)
System.out.print(arr[i] + " ");
System.out.println();
System.out.println("Modified Index array is: ");
for(int i = 0; i < n; i++)
System.out.print(index[i] + " ");
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 code to reorder an array
# according to given indices
def heapify(arr, index, i):
largest = i
# left child in 0 based indexing
left = 2 * i + 1
# right child in 1 based indexing
right = 2 * i + 2
global heapSize
# Find largest index from root,
# left and right child
if (left < heapSize and
index[left] > index[largest]):
largest = left
if (right < heapSize and
index[right] > index[largest]):
largest = right
if (largest != i):
# Swap arr whenever index is swapped
arr[largest], arr[i] = arr[i], arr[largest]
index[largest], index[i] = index[i], index[largest]
heapify(arr, index, largest)
def heapSort(arr, index, n):
# Build heap
global heapSize
for i in range(int((n - 1) / 2), -1, -1):
heapify(arr, index, i)
# Swap the largest element of
# index(first element) with
# the last element
for i in range(n - 1, 0, -1):
index[0], index[i] = index[i], index[0]
# Swap arr whenever index is swapped
arr[0], arr[i] = arr[i], arr[0]
heapSize -= 1
heapify(arr, index, 0)
# Driver Code
arr = [ 50, 40, 70, 60, 90 ]
index = [ 3, 0, 4, 1, 2 ]
n = len(arr)
global heapSize
heapSize = n
heapSort(arr, index, n)
print("Reordered array is: ")
print(*arr, sep = ' ')
print("Modified Index array is: ")
print(*index, sep = ' ')
# This code is contributed by avanitrachhadiya2155
C#
// C# code to reorder an array
// according to given indices
using System;
using System.Collections.Generic;
class GFG{
static int heapSize;
public static void heapify(int[] arr,
int[] index,
int i)
{
int largest = i;
// left child in 0 based indexing
int left = 2 * i + 1;
// right child in 1 based indexing
int right = 2 * i + 2;
// Find largest index from root,
// left and right child
if (left < heapSize &&
index[left] > index[largest] )
{
largest = left;
}
if (right < heapSize &&
index[right] > index[largest] )
{
largest = right;
}
if (largest != i)
{
// Swap arr whenever index is swapped
int temp = arr[largest];
arr[largest] = arr[i];
arr[i] = temp;
temp = index[largest];
index[largest] = index[i];
index[i] = temp;
heapify(arr, index, largest);
}
}
public static void heapSort(int[] arr,
int[] index,
int n)
{
// Build heap
for(int i = (n - 1) / 2 ; i >= 0 ; i--)
{
heapify(arr, index, i);
}
// Swap the largest element of
// index(first element)
// with the last element
for(int i = n - 1 ; i > 0 ; i--)
{
int temp = index[0];
index[0] = index[i];
index[i] = temp;
// Swap arr whenever index
// is swapped
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapSize--;
heapify(arr, index, 0);
}
}
// Driver Code
static void Main()
{
int[] arr = { 50, 40, 70, 60, 90 };
int[] index = { 3, 0, 4, 1, 2 };
int n = arr.Length;
heapSize = n;
heapSort(arr, index, n);
Console.WriteLine("Reordered array is: ");
for(int i = 0 ; i < n ; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
Console.WriteLine("Modified Index array is: ");
for(int i = 0; i < n; i++)
Console.Write(index[i] + " ");
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript code to reorder an array
// according to given indices
let heapSize;
function heapify(arr,index,i)
{
let largest = i;
// left child in 0 based indexing
let left = 2 * i + 1;
// right child in 1 based indexing
let right = 2 * i + 2;
// Find largest index from root,
// left and right child
if (left < heapSize &&
index[left] > index[largest] )
{
largest = left;
}
if (right < heapSize &&
index[right] > index[largest] )
{
largest = right;
}
if (largest != i)
{
// swap arr whenever index is swapped
let temp = arr[largest];
arr[largest] = arr[i];
arr[i] = temp;
temp = index[largest];
index[largest] = index[i];
index[i] = temp;
heapify(arr, index, largest);
}
}
function heapSort(arr,index,n)
{
// Build heap
for(let i = (n - 1) / 2 ; i >= 0 ; i--)
{
heapify(arr, index, i);
}
// Swap the largest element of
// index(first element)
// with the last element
for(let i = n - 1 ; i > 0 ; i--)
{
let temp = index[0];
index[0] = index[i];
index[i] = temp;
// swap arr whenever index is swapped
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapSize--;
heapify(arr, index, 0);
}
}
// Driver code
let arr=[50, 40, 70, 60, 90 ];
let index=[3, 0, 4, 1, 2];
let n = arr.length;
heapSize = n;
heapSort(arr, index, n);
document.write("Reordered array is: <br>");
for(let i = 0 ; i < n ; i++)
document.write(arr[i] + " ");
document.write("<br>");
document.write("Modified Index array is: <br>");
for(let i = 0; i < n; i++)
document.write(index[i] + " ");
// This code is contributed by ab2127
</script>
Producción:
Reordered array is: 40 60 90 50 70 Modified Index array is: 0 1 2 3 4
Complejidad de Tiempo: O(n log n)
Espacio Auxiliar: O(1)
Otro método para resolver el problema es con el espacio La complejidad de O (1) es: –
Intercambie los elementos presentes en el arr hasta que index_arr[i] no sea igual a i.
Ejecutemos en seco el siguiente código para la entrada dada: –
1ra iteración :- (i=0)
ar = [ 50, 40, 70, 60, 90 ]
array_índice = [3, 0, 4, 1, 2]
ya que index_arr[i] no es igual a i
intercambie el contenido presente en arr[i] con arr[index[i] y, de manera similar, intercambie también index_arr. Después de intercambiar tendremos los siguientes valores arr e index_arr:-
ar = [ 60, 40, 70, 50, 90 ]
array_índice = [1, 0, 4, 3, 2]
Dado que index_arr[0] no es igual a i.
volvemos a intercambiar el contenido presente en i con index_arr[i] para ambas arrays (arr , index_arr).
ar = [ 40, 60, 70, 50, 90 ]
array_índice = [0, 1, 4, 3, 2]
2.ª iteración:- (i=1)
Dado que el valor de index_arr[i] == i ; la condición bajo el bucle while no se ejecuta ya que la condición bajo las llaves se vuelve falsa y, por lo tanto, pasa a la siguiente iteración:
3ra Iteración :- (i=2)
Dado que el valor de index_arr[i] no es igual a i. Cambia el contenido.
Después de intercambiar obtendremos: –
ar = [ 40, 60, 90, 50, 70 ]
index_arr = [0, 1, 2, 3, 4].
Ahora, para la siguiente iteración (4.ª y 5.ª iteración), ya que el Valor de index_arr[i] es igual a i . simplemente omitimos ese ciclo (porque la condición bajo el ciclo while se vuelve falsa y, por lo tanto, el ciclo while no se ejecuta) y pasamos a la siguiente iteración.
C++
// A O(n) time and O(1) extra space C++ program to
// sort an array according to given indexes
#include <iostream>
using namespace std;
// Function to reorder elements of arr[] according
// to index[]
void reorder(int arr[], int index_arr[], int n)
{
// Fix all elements one by one
for (int i = 0; i < n; i++) {
// While index[i] and arr[i] are not fixed
while (index_arr[i] != i) {
swap(arr[i], arr[index_arr[i]]);
swap(index_arr[i], index_arr[index_arr[i]]);
}
}
}
// Driver program
int main()
{
int arr[] = { 50, 40, 70, 60, 90 };
int index[] = { 3, 0, 4, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
reorder(arr, index, n);
cout << "Reordered array is: \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << "\nModified Index array is: \n";
for (int i = 0; i < n; i++)
cout << index[i] << " ";
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// A O(n) time and O(1) extra space Java program to
// sort an array according to given indexes
class ReorderArray {
public static void swap(int arr[], int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// Function to reorder elements of arr[] according
// to index[]
public static void reorder(int arr[], int index_arr[],
int n)
{
// Fix all elements one by one
for (int i = 0; i < n; i++) {
// While index[i] and arr[i] are not fixed
while (index_arr[i] != i) {
swap(arr, i, index_arr[i]);
swap(index_arr, i, index_arr[i]);
}
}
}
// Driver program
public static void main(String[] args)
{
int arr[] = { 50, 40, 70, 60, 90 };
int index[] = { 3, 0, 4, 1, 2 };
int n = arr.length;
reorder(arr, index, n);
System.out.print("Reordered array is: \n");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.print("\nModified Index array is: \n");
for (int i = 0; i < n; i++) {
System.out.print(index[i] + " ");
}
}
}
// This code is contributed by Tapesh(tapeshdua420)
Python3
# A O(n) time and O(1) extra space C++ program to
# sort an array according to given indexes
def swap(arr, i, j):
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
# Function to reorder elements of arr[] according
# to index[]
def reorder(arr, index_arr, n):
# Fix all elements one by one
for i in range(n):
# While index[i] and arr[i] are not fixed
while index_arr[i] != i:
swap(arr, i, index_arr[i])
swap(index_arr, i, index_arr[i])
# Driver program
if __name__ == "__main__":
arr = [50, 40, 70, 60, 90]
index = [3, 0, 4, 1, 2]
n = len(arr)
reorder(arr, index, n)
print("Reordered array is: ")
for i in range(n):
print(arr[i], end=" ")
print("\nModified Index array is: ")
for i in range(n):
print(index[i], end=" ")
# This code is contributed by Tapesh(tapeshdua420)
C#
// A O(n) time and O(1) extra space C# program to
// sort an array according to given indexes
using System;
public class Test
{
static void SwapNum(ref int x, ref int y)
{
int tempswap = x;
x = y;
y = tempswap;
}
// Function to reorder elements of arr[] according
// to index[]
static void reorder(int [] arr, int [] index, int n)
{
// Fix all elements one by one
for (int i = 0; i < arr.Length; i++)
{
// While index[i] and arr[i] are not fixed
while (index[i] != i)
{
SwapNum(ref arr[i], ref arr[index[i]]);
SwapNum(ref index[i], ref index[index[i]]);
}
}
}
// Driver Code
static void Main()
{
int[] arr = { 50, 40, 70, 60, 90 };
int[] index = { 3, 0, 4, 1, 2 };
int n = arr.Length;
reorder(arr, index, n);
Console.WriteLine("Reordered array is: ");
for(int i = 0 ; i < n ; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
Console.WriteLine("Modified Index array is: ");
for(int i = 0; i < n; i++)
Console.Write(index[i] + " ");
}
}
// This code is contributed by Aditya_Kumar
Javascript
<script>
// Javascript code to reorder an array
// according to given indices
// Function to reorder elements of arr[] according
// to index[]
function reorder(arr,index_arr,n)
{
// Fix all elements one by one
for(let i = 0 ; i < n ; i++)
{
// While index[i] and arr[i] are not fixed
while(index_arr[i]!=i)
{
let temp = arr[i];
arr[i] = arr[index_arr[i]];
arr[index_arr[i]] = temp;
let tmp = index_arr[i];
index_arr[i] = index_arr[index_arr[i]];
index_arr[index_arr[i]] = tmp;
}
}
}
// Driver code
let arr=[50, 40, 70, 60, 90 ];
let index=[3, 0, 4, 1, 2];
let n = arr.length;
reorder(arr, index, n);
document.write("Reordered array is: <br>");
for(let i = 0 ; i < n ; i++)
document.write(arr[i] + " ");
document.write("<br>");
document.write("Modified Index array is: <br>");
for(let i = 0; i < n; i++)
document.write(index[i] + " ");
// This code is contributed by Aarti_Rathi
</script>
Producción
Reordered array is: 40 60 90 50 70 Modified Index array is: 0 1 2 3 4
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(1)
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA