最少没有MOVES对数组进行排序？ [英] min no of MOVES to sort an array?
问题描述
给出一个由不同整数组成的数组，您可以从数组中删除一个元素并将其附加到它的末尾。这是一个MOVE，算作一个MOVE操作。查找排序数组所需的最小移动数。
Given an array of distinct integers.You can remove an element from the array and append it to the end of it.This is one MOVE and counted as one MOVE operation.Find the min no of moves required to sort the array.
推荐答案
据我了解，将元素移到末尾会将所有元素移到那个位置之后，从而将第三个元素移到的
As I understand it, moving an element to the end shifts all elements after that one place, so that moving the third element of
[a_1, a_2, a_3, a_4, a_5, a_6]
最终产生
[a_1, a_2, a_4, a_5, a_6, a_3]
如果该理解是正确的，则具有最小数量的策略移动是
If that understanding is correct, the strategy with the minimum number of moves is
- 如果数组已排序，请停止。
- 查找出现在前面的最小元素数组中较小的元素
- 将该元素移到末尾
-
转到1。
- if the array is sorted, stop.
- find the smallest element that appears before a smaller element in the array
- move that element to the end
go to 1.
Ex:
I/p: 8 6 1 7 5 2 3 9
Process:
8 6 1 7 2 3 9 5
8 1 7 2 3 9 5 6
8 1 2 3 9 5 6 7
1 2 3 9 5 6 7 8
1 2 3 5 6 7 8 9 -> sorted
So totally 5 moves to be done to sort an array.
证明：在每一步骤中，最终排序数组中按升序排列的元素的初始序列至少增加一个，因此算法终止。该算法仅在对数组排序时终止。
Proof: With each step, the initial sequence of elements of the final sorted array that are placed in ascending order in the array increases by at least one, therefore the algorithm terminates. The algorithm only terminates when the array is sorted.
每个数组元素最多移动一次。如果元素 v 在迭代 i 中移动，则所有元素< = v 在数组中以升序放置。移动任何元素> v 不会更改相对位置，因此，未选择 v 作为要在以后的任何迭代中移动的元素。
Each array element is moved at most once. If element v is moved in iteration i, afterward all elements <= v are placed in ascending order in the array. Moving any element > v doesn't change that relative placing, therefore v is not selected as the element to move in any later iteration.
当且仅当数组元素至少与要移动的第一个元素一样大时，才移动数组元素，例如 v_1 。
An array element is moved if and only if it is at least as large as the first to be moved, say v_1.
通过构造，移动的元素形成严格递增的序列，因此没有元素< v_1 已移动。
By construction, the moved elements form a strictly increasing sequence, thus no element < v_1 is moved.
移动 v_1 后，所有大于<$ c的元素$ c> v_1 放在数组中较小元素（即<$ c $ c> v_1 ，可能还有其他元素）的前面。更改元素 w>的相对位置的唯一方法。之后的v_1 和 v_1 是通过将 w 移到末尾，因此在某个步骤 w 必须移动。
After moving v_1, all elements larger than v_1 are placed before a smaller element (namely v_1, possibly others) in the array. The only way to change the relative placing of an element w > v_1 and v_1 afterward is by moving w to the end, therefore at some step w must be moved.
在任何排序顺序中，所有元素> = v_1 必须至少移动一次：
In any sorting sequence, all elements >= v_1 must be moved at least once:
v_1 必须一步移动，因为是 v_0< v_1 在原始数组中的 v_1 之后放置，并且是更改 v_0 和 v_1 正在移动 v_1 。
v_1 must be moved in some step because there is a v_0 < v_1 placed after v_1 in the original array and the only way to change the order of v_0 and v_1 is moving v_1.
以上，所有 w>在移动。 v_1 之后，必须至少移动一次v_1
By the above, all w > v_1 must be moved at least once after v_1 has been moved.
查找所需的移动次数可以在O（n）中完成，但是排序本身当然是二次的。
Finding the number of moves required can be done in O(n), but of course the sorting itself is quadratic.
找到第一个要移动的元素后， v_1 ，仅计算小于 v_1 所需元素的元素 k 那么移动次数为 n-k 。
After finding the first element to move, v_1, one simply counts the number k of elements smaller than v_1, the required number of moves is then n - k.
查找 v_1 ：（我原本以为是向前，结果却是向后的，如果向后走，那很简单。）
Finding v_1 in O(n): (I had originally thought forwards, which turned out to be backwards, if you go backwards, it is straightforward.)
首先，从阵列的末尾开始扫描，直到找到局部最小值或到达阵列的开始为止。如果您到达起点，则该数组已经排序，无需移动。否则，存储（局部）最小值的值以及紧接其前的元素的值作为暂定值f v_1 。然后继续进行操作，直到到达数组的开始为止；在每个步骤中，如果当前元素较小，则更新最小值；如果当前元素大于该元素，则尝试暂定 v_1 。最小值，但小于暂定 v_1 。
First, you scan from the end of the array until you have found a local minimum or have reached the start of the array. If you reach the start, the array is already sorted, no moves required. Otherwise, store the value of the (local) minimum, and the value of the element directly before as the tentative value f v_1. Then proceed further until you reached the start of the array, at each step updating the minimum if the current element is smaller, or the tentative v_1 if the current element is larger than the minimum but smaller than the tentative v_1.
int move_count(int *a, int n) {
int j = n-1;
while(j > 0 && a[j-1] < a[j]) --j;
if (j == 0) return 0; // the array is already sorted
// min_val holds the smallest element in the array after
// the currently investigated position, v_1 holds the smallest
// element after the current position that is larger than any later
int min_val = a[j], v_1 = a[j-1];
j -= 2;
while(j >= 0) {
if (a[j] < min_val) {
min_val = a[j];
} else if (a[j] < v_1) {
v_1 = a[j];
}
--j;
}
int count_smaller = 0;
for(j = 0; j < n; ++j) {
if (a[j] < v_1) ++count_smaller;
}
return n - count_smaller;
}
这篇关于最少没有MOVES对数组进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
