我正在尝试练习解决来自 Codeforces 的问题。它是通过将数组的元素移动到数组的开头或结尾来对数组进行排序。起初我认为它是最长的递增子序列,但在某些情况下它不起作用。例如,如果输入是 4,1,2,5,3,则 LIS 是 3,但问题的答案是将 4 移动到数组的末尾,然后将 5 移动到数组的末尾,这给了我们 2。另外我在这个 LIS 中尝试示例 1,6,4,5,9,8,7,3,2 是 1,4,5,9 但问题的答案是 1 和 2 之间的 7 次移动。我得到了知道我应该使用贪婪的方法但不太相关。有人可以帮助我吗?
最佳答案
我们可以看到,要对数组进行排序,每个元素只需要移动至多一个。
所以,为了最小化移动的次数,我们需要找到不移动的元素的最大数量。这些元素是最长的连续序列,它是序列(a0, a1, ... an)
with a(i + 1) = ai + 1
。
例如,
(4,1,2,5,3),最长的连续序列是(1,2,3)
(5,2,1,3,4),最长的连续序列是(2,3,4)
所以我们有我们的代码:
int[]longest = new int[n + 1];
int result = 0;
for(int i = 0; i < n; i++){
longest[data[i]] = longest[data[i] - 1] + 1;
result = max (longest[data[i]] , result);
}
print "Minimum number of move is " + (n - result)
解释:
在代码中,我使用了一个数组longest
,其中索引ith<
存储了最长的连续序列,该序列以值i
结束。
因此,我们可以看到 longest[i] = longest[i - 1] + 1
。
最长连续序列的结果是存储在longest
数组中的最大值。
关于arrays - 排序数组所需的最少操作数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34217775/