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

我想递归解决这个算法;我想检查数组中的所有值是否相同（或相等）。如果所有值都相等，则返回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); 
}

来源

2015-06-09 B Cronyn

你能举一个例子，算法返回错误的结果吗？ – Turing85

请为我们提供一个测试用例，一个样本输入数组和预期的输出。（我们用多维数组工作吗？这是javascript还是java？ – FrankerZ

如果你想测试它肯定不会通过（即使在Eran修复之后），试试一个巨大的数组。 – maaartinus

变化

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

到

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

start++传递的start递归调用原始值（这是后增量运算符的回报），所以你的递归永远不会结束，你可能会得到一个StackOverflowError。

来源

2015-06-09 16:08:54 Eran

另一种可能的解决方案是使用'++ start'而不是'start ++'。有关pre和postincrements的更多信息，您可以参考[此链接]（https://docs.oracle。 com/javase/tutorial/java/nutsyandbolts/op1.html） – Turing85

完美修复它，我还必须更改第2行和第3行（start> end）和（a.length == 0）条件，以返回true相反，我想这些测试是为了声明t而设立的帽子没有值意味着所有的值是相同的....（含糊/主观？） –

@BCronyn它是有道理的说，一个空阵列的所有值是相等的:) – Eran

简单地取数组的第一个值可能是最简单的，直到单个值不相同为止。

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

编辑：意识到这个答案是为了做到递归，我的答案并没有这样做。

来源

2015-06-09 16:15:31

好的答案不管...你是对的，当我被要求去发现所有的值是否相等时，寻找不等价值似乎都是违反直觉的。我会重构道路。 –

你可以使用传统的分治法来解决它。将数组分成两半，直到有两个元素，然后检查它们是否相等。然后征服他们并比较价值。类似这样的：

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

执行here。

来源

2015-06-09 16:49:02

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

回答

相关问题