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

Question

我从一个网站得到了这个编码问题。问题如下所示：

如果一个数组可以通过在其中一个数组中交换最多一对元素而获得，则称它们为相似的数组。给定两个数组，请检查它们是否相似。

例如，对于A = [1、2、3]和B = [1、2、3]，输出应该是areSimilar（A，B）= true。 这些数组相等，不需要交换任何元素。

对于A = [1、2、3]和B = [2、1、3]，输出应该是areSimilar（A，B）= true。 我们可以通过在B中交换2和1来从A中获得B。

对于A = [1、2、2]和B = [2、1、1]，输出应该是areSimilar（A，B）= false。 无论在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. A: [1, 2, 3]
   B: [1, 2, 3]

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

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

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

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

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

然而，每次尝试提交代码时，网站都会显示“INCORRECT”。它未能通过六个隐藏测试中的两个，我无法弄清原因。这是正确的代码吗？还有其他更简单的方法吗？

- FlarrowVerse

---

copyA = A 并不会复制一个数组，它只是给你另一个对同一数组的引用。因此，原始 数组会被排序。 - RealSkeptic

你做了多少次交换？A：[2，3，1] B：[1，3，2] - SMA

@RealSkeptic 对于复制数组，使用 A.clone() 方法是正确的吗？ - FlarrowVerse

这是因为您对原始数组进行了排序，然后比较的是已排序的数组，而不是原始数组！ - Rajeev Singh

我认为更简单的方法是避免排序，只需计算差异。如果恰好有两个差异，请看看交换是否会使它们相等。 - Ole V.V.

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

- Rajeev Singh

---

是的，我做了。我使用了clone()而不是System.arraycopy()。 - FlarrowVerse

现在您已经在使用Arrays，可以考虑使用Arrays.copyOf()来生成副本（自Java 6以来）。 - Ole V.V.

在比较数组副本之前，您需要对它们进行排序。此外，根据https://dev59.com/_Gct5IYBdhLWcg3wWMFF的共识，`.clone()`优于`Arrays.copyOf()`。 - Klitos Kyriacou

@KlitosKyriacou 谢谢...我完全错过了那个声明。 - Rajeev Singh

@KlitosKyriacou，那些回答似乎只关注性能。这是选择的最不重要的标准。我坚持我的建议使用Arrays.copyOf()。 - Ole V.V.

@OleV.V. 我也认为 clone() 更易读，除非您想要更改数组复制的长度。我想这是个人偏好的问题。 - Klitos Kyriacou

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

使用Sets代替排序

不需要拷贝、排序和比较两个数组，可以直接使用set。排序的目的是为了检查两个数组是否完全相同。在这种情况下，可以将元素放入集合中并比较集合，而无需进行排序。

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

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

如果您的数组保证没有重复值，则集合方法将起作用。对于带有重复值的数组，频率映射可能有效，但实际上这会使内容难以理解。

一种线性方法是可以解决该问题的，因为只需要线性时间和恒定内存，而您的方法由于排序需要O(n log n)的时间，另外还需要线性内存。

步骤如下：

1. 检查数组长度是否相等，如果不相等，则返回false。

2. 创建一个包含两个元素的索引数组ind，表示存在差异的位置。

3. 遍历数组（与您现在所做的相同），计算差异。

4. 如果遇到差异，如果countSwap < 2，则将i放入ind[countSwap]，然后递增countSwap。

5. 在循环结束时，如果countSwap为0，则返回true。

6. 如果countSwap为1或大于2，则返回false。

7. 如果countSwap为2，则检查您保留的索引处的项目。如果A[ind[0]] == B[ind[1]]且A[ind[1]] == B[ind[0]]，则返回true，否则返回false。

解释如下：

如果两个数组之间有1个或3个及以上的差异，则它们肯定不是“相似”的。

但是，如果恰好有2个差异，这可能是因为这两个位置完全不同，也可能是因为存在交换。

因此，您需要检查这2个差异是否是由于交换引起的。

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

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

- RealSkeptic

---

集合不足以精确比较。考虑数组[1, 1, 1, 3]和[1, 3, 3, 3]。你的集合将是相同的，交换次数将为2，因此它们可能被认为是相似的，但实际上并不是。使用排序后的数组而不是集合将确保发现它们不能相似。 - Ole V.V.

@OleV.V. 对的，我正准备加上一条注释。 - RealSkeptic

Answer 3

areSimilar([4, 6, 3],[3, 4, 6]); // example arrays


boolean areSimilar(int[] a, int[] b) {
    
    boolean isSimular = false;
        int count = 0;
        int temp = 0;
        
        if(a.length!=b.length) { // check two arrays length
            return false;
        }
        
        for (int i = 0; i < a.length; i++) {
            if (a[i] == b[i]) {
                isSimular=true;
            } else {
                count++;
                if(count>1) {
                    isSimular =false;
                    return isSimular;
                } 
                for (int j = 0; j < a.length; j++) {
                    if(a[i]==b[j] && a[j]!=b[j]) {
                                                
                        temp=b[i];
                        b[i]=b[j];
                        b[j]=temp;
                        break;
                        
                        
                        
                        
                    }
                }
            }
        }

        
        return isSimular;
}

- Arman

---

虽然这段代码可能解决了问题，但是包括解释它如何以及为什么解决了问题将有助于提高您的帖子质量，并可能导致更多的赞。请记住，您正在回答未来读者的问题，而不仅仅是现在提问的人。请[编辑]您的答案以添加解释并指出适用的限制和假设。 - Adrian Mole

Answer 4

def areSimilar(a, b):
    n = 0
    if len(a)!=len(b):
        return False
    else:
        for i in range(len(a)):
            if a[i]!=b[i]:
                n+=1
                if n>2:
                    return False
            if a[i] not in b:
                return False
        print(n)
        return True

- Rishub Cheddlla

---

感谢您贡献答案。您能否编辑您的回答并包括一些有关代码的解释呢？这将有助于未来的读者更好地理解正在发生的事情，特别是那些对该语言感到陌生并难以理解相关概念的社区成员。 - STA