CareerCup Rearrange an array using swap with 0

本文主要是介绍CareerCup Rearrange an array using swap with 0，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Rearrange an array using swap with 0. 

You have two arrays src, tgt, containing two permutations of the numbers 0..n-1. You would like to rearrange src so that it equals tgt. The only allowed operations is “swap a number with 0”, e.g. {1,0,2,3} -> {1,3,2,0} (“swap 3 with 0”). Write a program that prints to stdout the list of required operations. 

Practical application: 

Imagine you have a parking place with n slots and n-1 cars numbered from 1..n-1. The free slot is represented by 0 in the problem. If you want to rearrange the cars, you can only move one car at a time into the empty slot, which is equivalent to “swap a number with 0”. 

Example: 

src={1,0,2,3}; tgt={0,2,3,1};

------------------------------------------------------------------------------------------------------------------

You can use an extra O(n) space to get a solution with O(n) time complexity. 

1. In a pre-processing step, go through the "source" array, compute the position of each of the 0 to n elements and store in the auxiliary 'position' array. 
2. Start at the heads of both source and target array and compare the elements
3. If the elements are the same or the value of the target array ==0 proceed to the next elements. Otherwise go to step 4
4. Find position of 0 using the 'position' array and swap it with the current element 'e' in the source array and update the positions of 0 and 'e' in the position array. Now swap 0 with the target element(found again using the position array) and after the swap, update their positions in the position array. Advance the pointers of both source and target arrays.
5. Repeat steps 3 & 4 until all the elements are processed.

这篇关于CareerCup Rearrange an array using swap with 0的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---