Java代码检查两个数组是否相似

Question

我从网站上遇到了这个编码问题。问题如下:

Two arrays are called similar if one can be obtained from another by swapping at most one pair of elements in one of the arrays.

Given two arrays, check whether they are similar.

Example

For A = [1, 2, 3] and B = [1, 2, 3], the output should be areSimilar(A, B) = true.

The arrays are equal, no need to swap any elements.

For A = [1, 2, 3] and B = [2, 1, 3], the output should be areSimilar(A, B) = true.

We can obtain B from A by swapping 2 and 1 in B.

For A = [1, 2, 2] and B = [2, 1, 1], the output should be areSimilar(A, B) = false.

Any swap of any two elements either in A or in B won't make A and B equal.

这是我给出的解决方案:

boolean areSimilar(int[] A, int[] B) {
    if(A.length != B.length) return false;

    int[] copyA = A, copyB = B;
    Arrays.sort(copyA); Arrays.sort(copyB); 
    int countSwap = 0;

    if(!Arrays.equals(copyA, copyB)) return false;

    for(int i = 0; i < A.length; i++) {
        if(A[i] != B[i]) countSwap++;
    }

    return (countSwap == 2 || countSwap == 0);
}

此代码为以下数组提供了正确的结果:

1. 答:[1,2,3]
   B:[1,2,3]

2. 答:[1,2,3]
   B:[2,1,3]

3. 答:[1,2,2]
   B:[2,1,1]

4. 答:[1,1,4]
   B:[1,2,3]

5. 答:[1,2,3]
   B:[1,10,2]

6. 答:[2,3,1]
   B:[1,3,2]

但每次我尝试提交代码时，网站仍然显示“INCORRECT”。它未能通过六项隐藏测试中的两项，我不明白为什么。这是正确的代码吗？还有其他更简单的方法吗？

Answer 1

您的代码不起作用，因为您在此处对原始数组进行了排序...

copyA = A, copyB = B;
Arrays.sort(copyA); Arrays.sort(copyB);

然后您将比较排序后的数组而不是原始数组，以检查它们是否可以仅使用一次交换进行转换!!

你应该做这样的事情......

boolean areSimilar(int[] A, int[] B) {
    if(A.length != B.length) return false;

    int countSwap = 0;
    int[] copyA = Arrays.copyOf(A, A.length);
    int[] copyB = Arrays.copyOf(B, B.length);

    // checking both contain the same elements...
    Arrays.sort(copyA); Arrays.sort(copyB); 
    if(!Arrays.equals(copyA, copyB)) return false; 

    // checking for min 2 swaps using original arrays...
    for(int i = 0; i < A.length; i++) {
        if(A[i] != B[i]) countSwap++;
    }

    return (countSwap == 2 || countSwap == 0);
}

更高效的解决方案...

boolean areSimilar(int[] A, int[] B) {
  ArrayList<Integer> ids = new ArrayList<>();
  for (int i = 0; i < A.length; i++) {
    if ( A[i] != B[i] ) {
      ids.add(i);
    }
  }
  if (ids.size() == 0) {
    return true;
  }
  if (ids.size() != 2) {
    return false;
  }
  int id1 = ids.get(0);
  int id2 = ids.get(1);
  if (A[id1] == B[id2] && A[id2] == B[id1]) {
    return true;
  }
  return false;
}