java - 计算 vector int[]中 "0"位置之间的 "1"位置总数

Question

有一个1和0的 vector :

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

我需要计算“1”位置之间的“0”位置总数。例如，如果 <0,1,0,0,1,0>则答案为2。但是，问题是该 vector 可能包含以下值:

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。然后，如果您找到了两者，请计算它们之间的 0。

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++;
    }
}

它可能可以优化为一个循环。