algorithm - 找到最小的片数，以便可以重新排列原始序列以形成所需的序列(时间限制)

Question

任何人都可以给我一个提示，如何为下面的问题找到有效的解决方案？

我可以解决一些小输入的问题，但在解决更困难的情况(例如，具有 450000 个元素和时间限制约 5.5 秒的数组)时，我超出了时间限制。

You are given two arrays with numbers from 1 to N written in random order.

Example:

// numbers from 1 to 4
int[] o = new int[] { 1, 4, 3, 2 }; // original
int[] d = new int[] { 1, 2, 4, 3 }; // desired

Find the minimum number of pieces of the original sequence so that those pieces can be rearranged to form the desired sequence.

In the example case above the minimal number of pieces is 3, as the original sequence:

{1, 4, 3, 2}      // original

can be split into:

{1}, {4, 3}, {2}

and those pieces can be rearranged to form the desired sequence:

{1}, {4, 3}, {2}
{1}, {2}, {4, 3}
{1, 2, 4, 3}      // desired

Answer 1

这是一个以 O(n) 运行的版本。这个想法是替换数字，使目标数组变为 [0, 1, 2, 3, ...] 然后计算所需切割的数量非常简单。这是 Javascript 中的一个实现( link ):

function solve(o, d) {
  var sub = [], count = 0;
  // make arrays 0-based and calculate substitution
  for (var i = 0; i < d.length; i++) {
    o[i]--;
    d[i]--;
    sub[d[i]] = i;
  }
  // substitute
  for (var i = 0; i < o.length; i++)
    o[i] = sub[o[i]];
  // scan and count
  for (var i = 1; i < o.length; i++)
    if (o[i - 1] + 1 != o[i])
      count++;
  return count + 1; // the number of pieces is the number of required cuts + 1
}

alert(solve([1, 4, 3, 2], [1, 2, 4, 3]));