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

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

我们可以看出，要对数组进行排序，每个元素最多只需要移动个

所以，为了最小化移动的次数，我们需要找到不移动的元素的最大数量。这些元素是 longest continuous sequence ，即 (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 存储最长的连续序列，该序列结束于 value i。

所以，我们可以看到longest[i] = longest[i - 1] + 1。

最长连续序列的结果是存储在longest数组中的最大值。

Answer 2

我在比赛期间在 Codeforces 上解决了这个问题。好问题。

想想'longest continuous sub-sequence'。答案是n-最长的连续子序列。
示例：取1 2 3 7 5 6 4。最长的连续子序列是1 2 3 4。现在你可以将剩余的元素按特定顺序移动，得到排序数组总是。至少我的直觉是这样想的

这是主要代码的片段：

    int n=in.readInt();
    int[] a=new int[n+1];
    int[] cnt=new int[n+1];
    int max=0;
    for(int i=0;i<n;i++)
        a[i]=in.readInt();
    for(int i=0;i<n;i++)
    {
        cnt[a[i]]=1+cnt[a[i]-1];
        max=Math.max(max,cnt[a[i]]);
    }
    out.printLine((n-max));

希望对您有所帮助！

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

minimum number of actions needed to sort an array

arrays

algorithm

sorting

greedy