检查数组是否对称

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


}  

测试用例： 除了第一个，我通过了所有的测试，但是当我运行第一个测试时，我得到了一个no。我认为问题在于中间有两个2。而且我并不确定代码是否能够简化。 时间复杂度是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 否

- Moe

---

但是5 8 2 2 8 5 是 对称的。 - Popnoodles

将一个打印命令添加到您的函数中，这样您就可以在每次递归时看到i和n的内容。然后，您可以使用它来帮助遍历您的if（）语句，并查看每个语句何时触发。 - DiMono

顺便说一句，这个检查 if((i == n-1-i) && (A[i] == A[n-1-i] )) return true; 是冗余的，可以简化为 if(i == n-1-i) return true; 你甚至可以使用 || 运算符将此情况与 n == 1 情况结合起来。 - Tuxdude

@pamphlet 哦，我看到你的答案在下面了... - Popnoodles

@popnoodles 是的，它是对称的，但我的输出是“否”。 :) - Moe

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(n+1)。你可以进行一些调整来去掉+1，但这会导致代码整体运行变慢。

- DiMono

---

@DiMono 不是 O(n+1)=O(n) 吗？在 O 表示法中，只有多项式中的最高次幂才有影响。 - Dheeraj Bhaskar

Answer 2

if(A[i] == A[n-1-i] && i < n/2 )

那一行就是问题所在。因为您正在使用两个以上的偶数值，当代码执行到这行时，它会跳过它，因为此时i = n/2，而不是小于其中任何一个数。所以函数跳过了这个值并继续执行return false。更改它为以下内容即可解决问题：

if(A[i] == A[n-1-i] && i <= n/2 )

- DiMono

---

不是真的。事实上，如果 i >= n/2，你应该返回 true。 - Ivaylo Strandjev

@DiMono 都不起作用！问题就像你说的那样，因为我使用的是大于2的偶数，我不太确定该怎么处理！ - Moe

Answer 3

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner input = new Scanner(System.in);

    int N;
    int i;
    boolean sym = true;

    N=input.nextInt();
    int [] numbers = new int [N];

    for (i=0; i<N; i++){
        numbers[i]= input.nextInt();
    }
    for(i=0;i<N;i++){
        if(numbers[i]!= numbers[N-1-i]){
        sym=false;}
    }

   if(sym==true){
       System.out.println("The array is a symetrical array");
   }
   else{
       System.out.println("The array is NOT a symetrical array");
   }
}

}

- Engin Yıldız

Answer 4

这个检查是无用的：

if((i == n-1-i) && (A[i] == A[n-1-i] ))
    return true;   

当然，如果两个索引相同，那里的值将匹配。

此外，您需要将此if语句拆分为两个：

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

如果i >= n/2则返回true。

否则会出现这样的情况：当i > n/2时（这意味着你已经知道你的数组是对称的），你不会进入那个if语句，从而返回false，这是错误的。

- Ivaylo Strandjev

---

如果我把它们分开，即使数组对称，当i >= n/2时它也会返回true，不是吗？ - Moe

Answer 5

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner input = new Scanner(System.in);

    int N;
    int i;


    N=input.nextInt();
    int [] numbers = new int [N];

    for (i=0; i<N; i++){
        numbers[i]= input.nextInt();
    }
    i=0;
    while (i<N/2&& numbers[i] == numbers [N-1-i]){i++;
    }

   if(i==N/2){
       System.out.println("The array is a symetrical array");
   }
   else{
       System.out.println("The array is NOT a symetrical array");
   }
        }

- Engin Yıldız