arrays - 排序数组所需的最少操作数

Question

我正在尝试练习解决来自 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 次移动。我得到了知道我应该使用贪婪的方法但不太相关。有人可以帮助我吗？

Answer 1

我们可以看到，要对数组进行排序，每个元素只需要移动至多一个。

所以，为了最小化移动的次数，我们需要找到不移动的元素的最大数量。这些元素是最长的连续序列，它是序列(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数组中的最大值。