检测输入字符串中的所有无效零索引(我有修改算法)

Question

我的要求如下:

输入:一个整数数组(值将仅为0/1)和整数ζ

进程:检测无效零的所有索引

一个无效零是属于0的运行,其长度大于或等于ζ零

输出:ArrayList包含无效零的所有索引

例:

input:  Data: 1,0,0,0,1,1,1,1,1,0,1,0,1,0,1,1,0,0,1,1,1,1        
    ? : 2

output: 2,3,4,17,18

============================================

我使用以下算法,想知道是否有更好的方法吗？

算法:验证(A [1 ... n],ζ)

Counter ? 0
For i ? 1 to n do
    if A[i] == 0 then 
        counter ? counter +1
        if i == n and counter >= ? then
            for j ? (n-counter)   to n do
                R.add(j)
    else
        if counter >= ?
            for j ? (i-counter-1)   to (i-1) do
                R.add(j)
        counter ? 0
return R

谢谢

Answer 1

我得到了这个O(n)算法,虽然看起来有点长.

Algorithm: validate(A[1…n], ?)
    j ? 0

    // Store all indices of zeroes in Q
    for i ? 1 to n do
    if A[i] == 0 then
        j ? j + 1
        Q[j] ? i

    Qsize ? j

    // if number of zeroes in input is less than ?, return empty set
    if Qsize < ? then
        return R //R is an Empty ArrayList

    //if any zero is invalid, return every index in Q
    if ? == 1 then
        for i ? 1 to Qsize do
            R.add(Q[i])
        return R

    flag ? false
    // one loop to indentify valid zeroes, change their indices to 0
    // only keep invalid zeroes indices in Q
    for i ? Qsize to ? do   

        if Q[ i – ? +1] – (i - ? +1) == Q[i] – i then
            flag ? true
            i ? i – ? +1 // for-loop will do one more i ? i -1

        else if flag == true and Q[i] - i <> Q[ i + 1 ] – (i + 1) then
            flag ? false
            i ? i  +1 // for-loop will do one more i ? i -1

        else
            Q[i] ? 0

    // Put invalid zeroes indices into R to return
    for i ? 1 to Qsize do
        if Q[i] <> 0 then
            R.add(Q[i])

    return R