计算分割点的数量

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"one_answers"4"。

整数范围从1到100000

复杂性需要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阵列来检测何时不能再具有分割点来避免最后一次传递。这只是一个练习。