подсчитывает количество разделяемых точек

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 до 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, чтобы определить, когда вы больше не можете иметь точку разделения. Это остается как упражнение.