两个数组之间的差异

Question

可能重复：
java中arraylist的交/并集

您好，我有两个字符串数组。我想要打印出两个数组之间的差异。有没有Java方法可以做到这一点？例如：

String[ ] first={"A","B","C"};
String[ ] second={"C","B"};

并且结果必须是"A"。

感谢所有的评论。

- ademcu

---

和这个问题一样：https://dev59.com/gW435IYBdhLWcg3wrSBB？ - CodeDreamer

1. 顺序很重要吗？
2. 重复元素怎么处理？
3. 第二个数组中新增的元素怎么处理？
4. 每个不同之处的索引怎么处理？......最重要的是：你能否提供一些更不那么琐碎的例子，以便我们可以理解你到底在问什么？

- thkala

这篇文章讲的是差异，而不是交集或并集。它与5283047没有重叠部分。 - fredt

@fredt 是的，但我们可以通过交集、删除和连接来获取差异 :) - Oleg Mikheev

@Oleg，当然可以，但这是一种次优的方式。这个问题正在得到回答，它没有被现有的问题所覆盖，也不应该被删除。 - fredt

Answer 1

将数组转换为Set<String>。

new HashSet<String>(Arrays.asList(array));

并且执行

Set<String> commonOnes = biggerSet.retainAll(smallerSet);
biggerSet.removeAll(commonOnes).add(smallerSet.removeAll(commonOnes))

或者使用guavadifference()

- jmj

---

这会获取在较小的数组中但不在较大的数组中的元素吗？ - jonhopkins

只有在以下情况下才有效：1. 顺序不重要，2. 如果一个元素在其中一个列表中出现两次，在另一个列表中出现一次仍然意味着相等。这可能适用于提问者，但需要警告... - mprivat

集合中不会存在重复元素。 - jmj

将巨大的数组转换为哈希集会使性能急剧下降。 - Oleg Mikheev

@fgb 嗯...不将其转换为哈希集，而是在列表上使用retainAll？ - Oleg Mikheev

retainAll 方法返回一个布尔值并修改了 Set。该方法的 Javadoc 表示：“从此集合中移除那些未包含在指定集合中的所有元素。” removeAll 的行为类似，可以参考文档。 - Paul

Answer 2

这个程序运行时间为 O(n log n + m log m)，其中 n 是 first 的大小，m 是 second 的大小。它基本上是对数组进行排序，然后遍历每个数组，在每个机会添加不匹配的元素到 LinkedList 中，最后生成一个数组。之前版本的代码无法正确工作，因为较长列表中的尾部元素没有在末尾添加。

public class SetDifference {
    public static void main(String... args) {
        String[] arrA = {"1", "2", "3", "4", "5", "25", "10"};
        String[] arrB = {"1", "2", "10", "4", "30"};

        System.out.println(Arrays.toString(differences(arrA, arrB)));
    }

    public static String[] differences(String[] first, String[] second) {
        String[] sortedFirst = Arrays.copyOf(first, first.length); // O(n)
        String[] sortedSecond = Arrays.copyOf(second, second.length); // O(m)
        Arrays.sort(sortedFirst); // O(n log n)
        Arrays.sort(sortedSecond); // O(m log m)

        int firstIndex = 0;
        int secondIndex = 0;

        LinkedList<String> diffs = new LinkedList<String>();  

        while (firstIndex < sortedFirst.length && secondIndex < sortedSecond.length) { // O(n + m)
            int compare = (int) Math.signum(sortedFirst[firstIndex].compareTo(sortedSecond[secondIndex]));

            switch(compare) {
            case -1:
                diffs.add(sortedFirst[firstIndex]);
                firstIndex++;
                break;
            case 1:
                diffs.add(sortedSecond[secondIndex]);
                secondIndex++;
                break;
            default:
                firstIndex++;
                secondIndex++;
            }
        }

        if(firstIndex < sortedFirst.length) {
            append(diffs, sortedFirst, firstIndex);
        } else if (secondIndex < sortedSecond.length) {
            append(diffs, sortedSecond, secondIndex);
        }

        String[] strDups = new String[diffs.size()];

        return diffs.toArray(strDups);
    }

    private static void append(LinkedList<String> diffs, String[] sortedArray, int index) {
        while(index < sortedArray.length) {
            diffs.add(sortedArray[index]);
            index++;
        }
    }
}

- durron597

---

更多的代码，但比asList的解决方法好得多。+1！ - ApproachingDarknessFish

这似乎不起作用。我的意思是它几乎可以工作！例如，String[] arrA = {"1", "2", "3", "4", "5", "25", "10"}; String[] arrB = {"1", "2", "10", "4", "30"}; 对于这两个数组，它返回25,3,30。它遗漏了5。 - OpenSource

@OpenSource 哇，我敢打赌它的工作原理一定比那更彻底。给我几分钟。 - durron597