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 没有
最佳答案
复杂的代码会导致更多的错误。因此,简化它。另外,寻找不平等而不是平等;检查一个错误比检查所有错误更容易。
// 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,但这会使代码整体运行速度变慢。
关于java - 检查数组是否对称,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15299312/