Hello Everyone,
Given two integer arrays of same size, “arr[]” and “index[]”, reorder elements in “arr[]” according to given index array. It is not allowed to given array arr’s length.
Example:
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]
Expected time complexity O(n) and auxiliary space O(1)
We strongly recommend you to minimize your browser and try this yourself first.
A Simple Solution is to use an auxiliary array temp[] of same size as given arrays. Traverse the given array and put all elements at their correct place in temp[] using index[]. Finally copy temp[] to arr[] and set all values of index[i] as i.
// 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;
}
Output:
Reordered array is: 40 60 90 50 70
Modified Index array is: 0 1 2 3 4
We can solve it Without Auxiliary Array . Below is algorithm.
- 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.
Below is implementation of above algorithm.
// 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;
}
Output:
Reordered array is: 40 60 90 50 70
Modified Index array is: 0 1 2 3 4
Another Method without using an auxiliary array is to sort the arrays.
Sort the index array and customize the sort to swap the arr[] data whenever you swap the index[] data.
//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;
}
Output:
Reordered array is: 40 60 90 50 70
Modified Index array is: 0 1 2 3 4
Time Complexity: O(nlogn)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above