需要在O(n)复杂性中解决的数组编码挑战

Question

我们给出了一个由n个数字组成的数组，一个数字x。我们需要在此数组中找到一个索引k，将数组分为两个部分（0至k-1，和K-1至N-1）这样：

在第一部分中等于x的元素数=第二部分中不等于x的元素数。

示例：

A = (5, 5, 1, 2, 3, 4, 5), X = 5
Answer: K= 4
(5, 5, 1, 2) contains two X's.
(3, 4, 5)  contains two non X's.

这种k总是根据问题描述存在。该解决方案需要具有O（N）的复杂性。o（n^2）解决方案太容易了，但是我找不到o（n）一个。

这是我到目前为止所拥有的：

int function(int X, vector<int> &A) {
    int k = 0;
    vector<int> indices;
    long count = A.size();
    int number_of_x= 0;
    for(int i=0;i<count;i++){
        if(A[i]==X)
            number_of_x++;
    }
    long part_one_x = 0;
    long part_two_nonx = 0;
    for(int i=0;i<count;i++){
        if(A[i]==X)
            part_one_x++;
        part_two_nonx = (count-i) - (number_of_x - part_one_x);
        if(part_one_x == part_two_nonx)
            k = i;
    }

    return k;
}

感谢您的帮助！

Answer 1

让我们考虑一下您的示例...

 A = (5, 5, 1, 2, 3, 4, 5)

如果您考虑第一个元素-5-，那么我们知道任何解决方案都必须在另一端具有一个非5值，因此我们向后工作以找到第一个非五个值，并跟踪"前面"one_answers"回到"我们正在工作...

 A = (5, 5, 1, 2, 3, 4, 5)
      ^              ^

因此，我们从末端工作时已经将5s与非5人保持平衡。现在，我们查看左侧的下一个位置，这也是五个位置，因此我们向左移动右侧位置，直到找到另一个非五个：

：

 A = (5, 5, 1, 2, 3, 4, 5)
         ^        ^

现在，我们推进了左侧位置，寻找另外五个，但在找到一个位置之前击中正确的位置，因此"右侧"位置是解决方案。