如果允许的唯一操作是就地移动,通过从索引A中删除一个元素并将其重新插入索引B,一次一个元素,您将如何生成正确的移动以结束排序的数组？同样,应该有长度(数组) – 长度(longestIncreasingSubsequence(array))移动所需.
例如,这是一个数组：
[ 1, 8, 5, 2, 4, 6, 3, 9, 7, 10 ]
增长最快的子序列是：
[ 1, 2, 4, 6, 7, 10 ]
这些要素的指数是：
[ 0, 3, 4, 5, 8, 9 ]
因此,我们需要移动的指数是：
[ 1, 2, 6, 7]
因为那些是尚未排序的索引.
为了得到排序数组,这4个元素的最终索引是：
[ 7, 4, 2, 8]
因此,我们需要同时将索引1移动到索引7,将索引2移动到索引4,将索引6移动到索引2,将索引7移动到索引8.问题是当移动元素时,其他元素会移动到后来的移动操作无效.我已经尝试过转换这些索引,但到目前为止还没有提出正确的移动列表.有任何想法吗？
希望我已经很好地解释了这个问题.请提问,我会澄清.谢谢！
您的问题是源位置以先前的顺序表示,而目标位置是最终的顺序.当您执行1-> 7时,您还不知道先前顺序中的7.您需要对所有动作进行调整.最初的举动是：
from: [ 1, 2, 6, 7] to: [ 7, 4, 2, 8]
步骤1
让我们首先转换位置,好像我们首先删除所有元素,然后将元素插入新位置.对于从位置,从左侧开始：在1档位(2,6,7)向下移动到(1,5,6).在1处移除再次将(5,6)向下移动到(4,5).在5档移动时将5向下移动到4.对于具有更大或相等索引的所有后续位置中的每个位置必须递减.我们得到：
from: [ 1, 1, 4, 4]
对于到位,从头到尾：位置8是正确的.位置2也是正确的,但这意味着先前(7,4)在插入时实际上是(6,3).所以我们调整它们.类似地,插入3表示先前位置6为5.
因此,对于to数组,我们从最后开始,对于每个位置,我们递减所有具有较大索引的先前位置. to数组变为：
to: [ 5, 3, 2, 8]
第2步
我们所拥有的是4次移除的正确位置,然后是4次插入.现在我们想要删除删除和插入.
必须在(1,1,4)的删除之前进行5的插入. 5大于这些中的任何一个,因此它不会影响位置(1,1,4),但是5会受到影响,因为在插入点的左侧进行了3次移除. 5变为8.
必须在(4,4)处的移除之前插入3.由于3小于4,因此位置3不受移除影响,但移除必须增加到位置(5,5).
插入2是在最后一次移除5之前(是4).它更小,因此5调整为6.
第2步的一般方法：
for i = 0 to size-1
for j = size-1 to i+1
if from[j] < to[i] then increment to[i]
else increment from[j]
我们应该得到数组：
from: [ 1, 1, 5, 6] to: [ 8, 3, 2, 8]
这些是在移动时使用正确位置执行的最终动作.移动可以从左到右读取：从1处移除,在8处插入.在1处移除,在3处插入3.在5处移除,在2处插入2.在6处移除,在8处插入.