Swapping elements with next smaller value_问答_开发者

Given an array of positive integer, we need to exchange each element with first element which is less than it(current element) as we move from left to right.

Example

{ 3 , 5 , 12, 2 ,11 }
{ 2 , 3 , 5 , 11, 12 }

Brute-force solution simulation for better understanding of the problem

{ 5, 11, 2, 7, 2 }
After first exchange  { 2, 11, 5, 7, 2} 
After second exchange { 2, 5, 11, 7, 2}
After third exchange  { 2, 5, 7, 11, 2}
After fourth exchange { 2, 5, 7, 2, 11}

Can anyone think of a solution which is better O(n^2). I was first thinking of maintaining a double ended queue and as we travel from first element towards right, we can try to maintain next smallest element of other in between.

Like for the First case, I will do something like this

while i am finding next element of 3, I will maintain a curr_next to 5. If before encountering the next small element for 3, i encounter one of 5, then I will enqueue it but it hardly improve the performance and still O(n^2)

EDIT: We have to move from left to right. Simulation of first example -

{ _3_ , 5 , 12, 2 ,11 }
{ 2,  _5- , 12, 3, 11 }
{ 2,  3, _12_ , 5, 11 }
{ 2, 3, 5, _12_,   11 }
{ 2, 3, 5,  11 ,   12开发者_运维问答 }

I can suggest a solution with O(n*logn) complexity based on usage of Segment Trees.

Algorithm:

Construct an array of pairs (value, index) which is formed from values and corresponding indexes of elements of the initial array. Let's call it array_2
Sort the obtained array by value.
Construct a Segment Tree on this array which allows us to find the element with minimal index on a given interval. Let's call it SegmentTree
Sequentially pass through the values array (the one initially given). For each element array[ i ] fing the element which it has to be swapped with as follows:

4.1. Find the value of the current element in the array_2 using binary search. Let it be found at some position k. After this all elements in the array_2 below position k are the elements in the original array which are smaller than the current one. As you will see later, all of them also have greater indexes than the current one (because we will remove the element with index i from array_2 after i-th step).

4.2. Now we have to find the element with minimal index in array_2 on interval [0, k-1]. This can be done querying the SegmentTree constructed on step 2. After we get the element with minimal index, we perform the corresponding swap in the original array, swap the indexes of these elements in array_2 (because they have been changed in the original array).

4.3. Perform two update operations on the SegmentTree - remove the element with index currently being processed in the original array, and update the value of index of the element which was swapped with the currently processed index.

After performing steps 4.1 - 4.3 n times we will obtain the target array.

Complexity:

We pass through the original array - n iterations. For each iteration we perform a binary search, a SegmentTree query and two SegmentTree updates, each of them taking logn time to perform. Summary O(n*logn).

The problem is not stated very well. After we exchange two elements, do we continue from the same position, and move right when no smaller element is found? Or do we move right immediately after the exchange? In the first case we end up with a sorted array.

In the second case I would maintain a balanced search tree of elements and indices. Start at the leftmost element, an repeat these steps:

Set I = 0, N = length A
Loop until I < N
1. Add the current element to the tree, with its index
2. Set L=-1
3. Repeat these steps
  1. Find the smallest element larger than A[I] in the tree.
  2. If there's such an element A[K] and K > L
    - swap A[I] and A[K] in the array
    - remove A[K] from the tree (it will not be swapped any more)
    - update index of the new A[I] in the tree
    - set L = K
  3. If there's no such element, finish and increment I