计算向量 int[] 中“1”位置之间的“0”位置总数

Question

有一个1和0的向量：

int[] vec = new int[6]{0,1,0,0,1,0};

我需要计算“1”位置之间的“0”位置总数。例如，如果 <0,1,0,0,1,0> 那么答案是 2。但是，问题是向量可能包含以下值：

int[] vec = new int[6]{0,1,0,0,0,0};  // the answer is 0

或

int[] vec = new int[6]{1,0,0,1,0,1};  / the answer is 3

到目前为止，我只是针对第一种情况（<0,1,0,0,1,0>）做了一个简单的算法。

    int start = 0, end = 0;
    for (int i=0; i<vec.length; i++)
    {
        if (vec[i] == 1 && start == 0)
            start = i;

        if (vec[i] == 1 && start != 0)
            end = i;
    }
    int result = end - start - 1;

我需要一些帮助来开发可以处理所有上述情况的更通用的算法。

Answer 1

您可以从两端遍历数组以找到第一个和最后一个 1。然后，如果你找到了两者，数一数它们之间的 0s。

int start = -1;
int end = vec.length;
int i = 0;
int j = vec.length-1;
while (i < j) {
    if (vec[i] == 1 && start < 0)
        start = i;
    i++;
    if (vec[j] == 1 && end >= vec.length)
        end = j;
    j--;
    if (start >= 0 && end < vec.length)
        break;
} 
int count = 0;
if (start >= 0 && end < vec.length) {
    for (i = start + 1; i < end; i++) {
        if (vec[i] == 0)
            count++;
    }
}

大概可以优化成一个循环

Answer 2

抱歉，最初我以为您想计算段数而不是实际的零数。

您可以计算第一个零 (n) 之后的所有零，跟踪自最后一个 (m) 以来零的数量。然后，当您到达向量的末尾时，n 的计数是 m 个零，太高了。

int count = 0;
int zeroesSinceLastOne = 0;
bool firstOneSeen = false;

for(int i = 0, n = vector.size(); i < n; ++i)
{
    while(!firstOneSeen && vector[i] == 0)
    {
        continue;
    }
    firstOneSeen = true;

    if(vector[i] == 0)
    {
        ++count; 
        ++zeroesSinceLastOne;
    }
    else
    {
        zeroesSinceLast = 0;
    }
}

return count - zeroesSinceLastOnce;

免责声明：未经测试。可能会给出错误的数字或杀死你的猫。

Answer 3

试试这个算法：

startIndex = -1;
endIndex = -1;
for i from 1 to vec.length():
   if( 1 == vec[i])
       startIndex = i
       break;
for i from vec.length() to 1:
   if( 1 == vec[i])
       endIndex = i
       break;
ans = endIndex - startIndex - no_of_ones_in_between

计算向量 int[] 中“1”位置之间的“0”位置总数

Calculation of a total number of "0" positions between "1" positions in a vector int[]

java

algorithm

vector