计算分裂点的数目

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数组来检测何时不再有拆分点来避免最后一次传递。这是一个练习。