arrays - [1 2 .. N] 排列的最长递增子序列

Question

问题是:

给定一个包含 N 个元素(1 到 N)的数组，使用一个约束对数组进行排序:您只能将一个元素移动到数组的开头或结尾。您至少需要多少步才能对数组进行排序？

例如:2 5 3 4 1 => 1 2 5 3 4 => 1 2 3 4 5，所以我需要至少 2 个 Action 。

我找到了一个解决方案:N - length of longest increasing subsequence，在上面的例子中，答案是 5 - 3 = 2。

我知道一个O(NlogN) 算法来寻找最长递增子序列 (LIS)。但是数组中的元素在 [1, N] 中，我想知道是否有一个 O(N) 的解决方案来找到数组的 LIS？

或者如果我们知道元素是从 1 到 N，是否有一个 O(N) 解决方案来解决初始问题？

Answer 1

您正在寻找的是最长的递增序列，其中任意两个连续元素之间的差为 1。

仅仅找到最长的递增序列是不够的，例如 1 5 3 4 2 最长的 inc seq 的长度为 3 但问题只能在据我所知，3 步不是 2。

要在 O(N) 时间和 O(N) 空间内找到差为 1 的最长 inc seq 可以完成例如，通过分配大小为 N 的 helper 数组初始化为所有 0。该数组将在 i 位置存储 i 最长子序列的长度，如果尚未看到 i ，它将是 0。

然后你遍历未排序的数组，当你找到一个元素 x 你设置 helper[x] = helper[x-1] + 1 然后你更新一个max 变量。

最后，排序的代价是input_array.length - max

例子:

array:   3 1 2
         0 1 2 3
helper:  0 0 0 0
max = 0

step 1:
check element at position 1 which is 3. helper[3] = helper[3 - 1] + 1 == 1:
          0 1 2 3
helper:   0 0 0 1
max = 1

step 2:
check element at position 2 which is 1. helper[1] = helper[1 - 1] + 1 == 1:
          0 1 2 3
helper:   0 1 0 1
max = 1

step 3:
check element at position 3 which is 2. helper[2] = helper[2 - 1] + 1 == 2:
          0 1 2 3
helper:   0 1 2 1
max = 2

cost = 3 - 2 = 1