用于检查两个阵列是否相似的Java代码

Question

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

如果可以通过交换其中一个阵列中的至多一对元素从另一个阵列获得一个阵列,则称这两个阵列是相似的.

给定两个数组,检查它们是否相似.

例

对于A = [1,2,3]和B = [1,2,3],输出应该是相似的(A,B)=真.

数组相等,无需交换任何元素.

对于A = [1,2,3]和B = [2,1,3],输出应该是相似的(A,B)=真.

我们可以通过在B中交换2和1从A获得B.

对于A = [1,2,2]和B = [2,1,1],输出应该是相似的(A,B)=假.

在A或B中任何两个元素的任何交换都不会使A和B相等.

这是我给出的解决方案:

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

Answer 2

你程序中的问题

您没有使用数组的副本创建和排序，而是使用了赋值。

copyA = A

这意味着它仍然是对原始copyA数组的引用，因此，当您尝试计算交换次数时，原始数组将被排序。

这意味着当您尝试检查两个具有相同元素但多次交换的数组时，您将true在应该得到false.

数组应该通过以下方式复制：

• A.clone()
• Arrays.copyOf(A, A.length)
• 或者copyA = new int[A.length]; System.arrayCopy(A,0,copyA,0,A.length);

集合而不是排序

您可以使用集合，而不是复制数组、排序和比较。排序的原因是检查两个数组是否具有完全相同的元素。在这种情况下，您可以将元素放入集合中并比较集合，而不需要排序。

Set<Integer> setA = new HashSet<>(Arrays.asList(A));
Set<Integer> setB = new HashSet<>(Arrays.asList(B));
if ( ! setA.equals(setB) ) {
    return false;
}

当且仅当两个集合包含完全相同的元素（集合中的顺序并不重要）时，equals集合的方法才会返回。true

仅当保证数组不具有重复值时，set 方法才有效。频率图可以适用于具有重复的数组，但坦率地说，它是不可读的。

线性方法

除了线性内存之外，由于排序的原因，您的方法需要 O(n log n) 。事实上，这个问题可以在线性时间和常数内存中得到解决。

• 检查长度是否相等。如果不是，则返回 false。
• 让ind为两个元素的数组，作为存在差异的位置的索引。
• 循环数组（就像现在一样）计算差异。
• 如果遇到差异，如果countSwap< 2，则输入i，ind[countSwap]然后递增countSwap。
• 循环结束时，如果countSwap为0，则返回true。
• 如果countSwap1 或大于 2，则返回 false。
• 如果countSwap是2，检查你保存的索引处的项目。如果A[ind[0]] == B[ind[1]]且A[ind[1]] == B[ind[0]]，则返回true，否则返回false。

解释

如果两个数组之间存在 1 或 3 个及以上差异，那么它们当然不是“相似”的。

但如果确实有 2 个差异，则可能是因为这两个地方的值完全不同，或者是因为存在交换。

因此，您检查这两个差异是否是由于交换造成的。

无需排序。排序的唯一原因是查看两个数组是否具有完全相同的元素。但差异的数量可以告诉你，无需排序。

countSwap顺便说一句，一旦达到 3，你就可以跳出循环。