如何使用递归检查数组中的所有值是否相等？

Question

我正在尝试以递归的方式解决这个算法问题；我想要检查数组中的所有值是否相同。如果所有值都相等，返回true，否则返回false。我的代码没有通过任何测试。

public boolean allEqual(int[] a, int start, int end){
    if (start > end) return false;
    if (a.length==0) return false;
    if (start==end && a[start] == a[end]) return true;
    if (a[start] != a[end]){
        return false;
    }
    return allEqual(a, start++, end);
} 

- B Cronyn

---

你能举个例子，算法返回错误结果的情况吗？ - Turing85

请提供一个测试用例、一个输入样本数组和期望的输出。（我们是在使用多维数组吗？这是 JavaScript 还是 Java？） - Blue

如果你想测试一下，它肯定不会通过（即使经过Eran的修复），可以尝试使用一个巨大的数组。 - maaartinus

没有任何借口（理由）可以递归地执行此操作 - 这是非常低效的，会在大型数组上导致堆栈溢出。此外，通过与数组中的最后一个元素进行比较，您故意读取非连续的内存块，这本身会减慢程序的运行速度。请不要在“真实”的代码中使用此方法！ - Floris

Answer 1

改变

return allEqual(a, start++, end);

to

return allEqual(a, start+1, end);

start++将start的原始值传递给递归调用（这就是后增运算符返回的内容），因此您的递归永远不会结束，您可能会得到一个StackOverflowError错误。

- Eran

---

еҸҰдёҖдёӘеҸҜиғҪзҡ„и§ЈеҶіж–№жЎҲжҳҜдҪҝз”Ё++startиҖҢдёҚжҳҜstart++гҖӮжңүе…ійў„еўһйҮҸе’ҢеҗҺеўһйҮҸзҡ„жӣҙеӨҡдҝЎжҒҜпјҢиҜ·еҸӮиҖғжӯӨй“ҫжҺҘгҖӮ - Turing85

完美。问题已解决。我还必须更改第2行和第3行的（开始>结束）和（a.length==0）条件，以返回true。我猜测试被设置为声明没有值意味着所有值都相同....（模糊/主观？） - B Cronyn

@BCronyn 说一个空数组的所有值都相等是有道理的 :) - Eran

@BCronyn 我认为 if (start > end) return false; 这一行可以直接删除，因为这个条件永远不会成立（递归在 start == end 时结束），除非你在初始调用中传递了无效的参数，在这种情况下抛出 IllegalArgumentException 更合理。 - Eran

Answer 2

最简单的方法可能是直接取数组的第一个值，然后一直遍历直到找到一个不同的值为止。

public void allEqual(int[] arr) {
    if(arr.length==0) return false;
    for(int i=0; i<arr.length; i++)
        if(arr[0]!=arr[i]) return false;
    return true;
}

编辑：意识到这个答案是用递归来实现的，而我的答案并没有那么做。

- Matthew Wright

---

好的回答，无论如何...你说得对，似乎很不合理去寻找不相等的值，当我被要求查找所有值是否相等。我会在以后进行重构。 - B Cronyn

Answer 3

你可以使用经典的分治方法来解决它。将数组分成两半，直到只剩下两个元素，然后检查它们是否相等。然后征服它们并比较值。像这样：

class Ideone {

    static boolean checkEquals(int a[], int start, int length) {

        if (length==2)
            return a[start]==a[start+1] && a[start]==a[0];
        else
            return checkEquals(a,start+0,length/2) &&
                   checkEquals(a,start+length/2,length/2);     
    }

    public static void main (String[] args) {
        int a[]={1,1,1,1,1,1,1,1};
        System.out.println(checkEquals(a,0,8));
    }
}

执行了

这里。

- Anindya Dutta

---

整数长度的一半加上整数长度的一半是否总是等于长度？尝试一些奇数长度。 - Patrick Parker