计算分裂点的数量

Question

我刚刚有一个关于计算整数数组中的分割点的问题，以确保两侧至少有一个重复的整数。

例如：

1 1 4 2 4 2 4 1

我们可以将其拆分为：

1 1 4 2 | 4 2 4 1

或

1 1 4 2 4 | 2 4 1

所以两边至少有一个'1','2','4'

整数可以在 1 到 100,000 之间

复杂度需要O(n)。如何解决这个问题？

Answer 1

遍历数组并构建 count[i] = how many times the value i appears in the array。只有 count[i] >= 2 对于所有非零值，该问题才可解。您可以使用此数组来判断数组中有多少个不同的值。

接下来，进行另一遍并使用另一个数组 count2[i]（或者您可以重复使用第一个数组），跟踪您何时至少访问了每个值一次。然后将那个位置作为你的分割点。

示例：

1 1 4 2 4 2 4 1
count = [3, 2, 0, 4] => 3 distinct values

1 1 4 2 4 2 4 1
^ => 1 distinct value so far
  ^ => 1 distinct value so far
    ^ => 2 distinct values so far
      ^ => 3 distinct values so far => this is your split point

可能存在没有解决方案的情况，例如如果最后一个 1 也在开头。要检测到这一点，您可以在决定分割点后再次遍历数组的其余部分，看看您是否仍然拥有那一侧的所有值。

您可以通过使用 count 和 count2 数组来检测何时不再有分割点，从而避免最后一次通过。这留作练习。

计算分裂点的数量

count the number of split points

algorithm

split