java - 检查数组是否对称

Question

public class symm
{


/* 
 * Returns true if array A is symmetric.
 * Returns false otherwise.
 * n is the number of elements A contains.
 *
 * The running time of your algorithm is O(  ).
 * You may add a brief explanation here if you wish.
 */

 public static boolean symmetric( int[] A, int n )
 {
 return symmHelper(A, n, 0);

 }

private static boolean symmHelper(int[] A, int n, int i) {
if(n==1)
    return true;
if((n==2) && (A[i] == A[n-1-i]))
    return true;
if((i == n-1-i) && (A[i] == A[n-1-i] ))
    return true;    

if(A[i] == A[n-1-i] && i < n/2 )
    return symmHelper(A, n, i+1);

return false;
}  


}  

测试用例:我通过了所有测试 ecxept the fitst on 每当我运行它时我都没有，我认为问题是中间有两个 2s。而且我不太确定代码，我认为它可以简化。运行时间是o(log n)吗？

5 8 2 2 8 5是的

10 7 50 16 20 16 50 7 10是的

5 8 5是的

1000 1000是的

6000是的

10 7 50 16 20 16 50 7 1000没有

10 7 50 16 20 16 50 700 10没有

10 7 50 16 20 16 5000 7 10没有

10 7 50 16 20 1600 50 7 10没有

10 7 50 16 1600 50 7 10没有

Answer 1

复杂的代码会导致更多的错误。因此，简化它。另外，寻找不平等而不是平等；检查一个错误比检查所有错误更容易。

// A = array, n = size of array, i = looking at now
private static boolean symmHelper(int[] A, int n, int i) {

    if (i > n/2)     // If we're more than halfway without returning false yet, we win
        return true;

    else if (A[i] != A[n-1-i])    // If these two don't match, we lose
        return false;

    else    // If neither of those are the case, try again
        return symmHelper(A, n, i+1);
}

如果我没有记错我的 O() 表示法，我认为这应该是 O(n+1)。您可以对此进行其他调整以删除 +1，但这会使代码整体运行速度变慢。