Java中的分而治之算法

Question

我必须用 Java 编写一个使用分而治之的技术。给定一个包含 n 个 int 元素的数组 V算法应计算两次连续的次数出现 0。

例：如果V = [3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2]，算法应返回3，请注意，0， 0， 0 对应于有 2 对连续的零。

我已经编写了如下程序，但是当我运行它时，它给了我一个ArrayIndexOutOfBoundsException。我做错了什么？

public class Test {
    public static void main(String[] args){
        int[] v = {3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2};
        System.out.println(Conta_Zeri_Main(v));
    }
    public static int Conta_Zeri_Main(int[] v){
        if (v.length == 0 || v.length == 1)
            return 0;
        else  
            return Conta_Zeri(v, 1, v.length);
    }
    public static int Conta_Zeri(int[] v, int i, int f){
        int m,result,sx,dx;
        if (i >= f)
            return 0;
        else{
            m = (i + f)/2;
            sx = Conta_Zeri(v, i, m);
            dx = Conta_Zeri(v, m+1, f);
            result = sx + dx;
            if ((v[m] == v[m+1]) && (v[m] == 0))
                result++;
            return result; 
        }
    }
}

Answer 1

除了已经指出的异常情况，

在您的代码中，您不检查是否v[m] = v[m+1] = 0 .当数组在 2 个连续的零之间分区时，这将错过一些可能性。

将 if 语句更改为：

if ( (m < v.length - 1 ) && (v[m] == v[m+1]) && (v[m] == 0) )