Shuffle an array according to the given order of elements


Given an array of distinct integers, shuffle an array according to the given order of elements.


 

For example,


Input: 

arr[] = { 1, 2, 3, 4, 5 }
pos[] = { 3, 2, 4, 1, 0 }

Output:

arr[] = { 5, 4, 2, 1, 3 }

i.e. if pos[i] = j, then update arr[j] = arr[i] for every index i.
In other words, update arr[pos[i]] = arr[i] for every index i.

 
Simple solution is to create an auxiliary array of size n and for each element in the input array, we set the corresponding values in the auxiliary array. After filling the auxiliary array, we copy it back to the given array. This can be implemented as follows in C.

 

Download   Run Code

Output:

5 4 2 1 3

 
We can also use a map in place of the auxiliary array as demonstrated below in C++:

 

Download   Run Code

Output:

5 4 2 1 3

 
Both above solutions take extra space. The algorithm can be implemented with O(1) extra space as shown below:

 

Download   Run Code

Output:

5 4 2 1 3

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading…

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Source link

Leave a Reply

Your email address will not be published. Required fields are marked *