在 Java 中获取两个列表之间的项目差异

我认为你的问题没有明确定义。我将尝试以这种方式指定它，以确保您的解决方案是正确的。

有两个列表，分别表示有序事物和已发送事物。缺少的对象只能发生在一个列表中。缺少对象的假设很重要，否则您的解决方案是不正确的。

可以使用 （Hash）Set 数据结构改进解决方案。ArrayList 中的 removeAll 方法具有二次时间复杂度，对于 HashSet，它是线性的（平均）。

如果您的列表可以包含重复项，则需要在使用 HashSet 时对其进行处理（例如，通过向对象添加一些唯一标识符）。

一般来说，我认为这是正确的方法，你需要从另一个中减去一个。 我只能想到这里和那里的轻微改进：

• 当您可以直接返回时，不需要 .此外，返回会直接删除一个嵌套级别（否"No difference"StringStringBuilderelse)
• 连接收集器允许设置前缀和后缀，以便您免费查看项目周围。Stream"
• 您可以考虑"x item(s) missing in list: "X", "Y"

private static String getDifference(List<String> order, List<String> sent) {
    if (new HashSet<>(order).equals(new HashSet<>(sent))) {
        return "No difference";
    }

    StringBuilder output = new StringBuilder();

    List<String> auxOrder = new ArrayList<>(order);
    auxOrder.removeAll(sent);
    if (!auxOrder.isEmpty()) {
        output.append(format(auxOrder, "sent"));
    }

    List<String> auxSent = new ArrayList<>(sent);
    auxSent.removeAll(order);
    if (!auxSent.isEmpty()) {
        output.append(auxOrder.isEmpty() ? "" : " & ");
        output.append(format(auxSent, "order"));
    }

    return output.toString();
}

private static String format(List<String> missing, String listName) {
    return "%s item(s) missing from %s : %s".formatted(
            missing.size(),
            listName,
            missing.stream().collect(Collectors.joining("\", \"", "\"", "\""))
    );
}

如果它们是大列表并且成本高昂，则可以通过事先检查列表的大小来提高性能，并且仅在第一个列表比第二个列表长时才执行此操作removeAllremoveAll

首先，是否存在重复项还不够清楚。其次，如果您不关心顺序，请不要使用 list equals（） 方法，因为在许多情况下，如果两个列表包含相同的项目但顺序不同，它会失败。

除此之外，该算法应该有效，但可以优化。我相信主要问题是，在大小为 n 的列表和大小为 m 的列表之间使用 removeAll（） 方法具有最差的时间复杂度 O（n*m）（二次），而您实际上可以达到 O（n+m） 的时间复杂度（线性）。如果你不关心重复，你可以稍微修改你的解决方案，以使用 HashSet 通过以下方式实现此目标：

// If duplicates are irrelevant
private static String getDifference(List<String> ordered, List<String> sent) {
    Set<String> orderedSet = new HashSet<>(ordered);
    Set<String> sentSet = new HashSet<>(sent);
    if (orderedSet.equals(sentSet)) {
        return "No difference";
    } else {
        StringBuilder output = new StringBuilder();
        orderedSet.removeAll(sent);

        if (!orderedSet.isEmpty()) {
            output.append(orderedSet.size()).append(" item(s) missing in sent: ");
            output.append("\"").append(String.join("\", \"", orderedSet)).append("\"");
        }

        sentSet.removeAll(ordered);

        if (!sentSet.isEmpty()) {
            if (output.length() > 0) {
                output.append(" & ");
            }

            output.append(sentSet.size()).append(" item(s) missing in ordered: ");
            output.append("\"").append(String.join("\", \"", sentSet)).append("\"");
        }

        return output.toString();
    }
}

如果你关心重复，那么你实际上不是在比较列表，而是在比较多集。对于多集实现，您可以使用 Guava 库。Multisets 的可能实现如下所示：

// If duplicates are relevant, with Guava
private static String getDifferenceWithDuplicates(List<String> ordered, List<String> sent) {
    Multiset<String> orderedSet = HashMultiset.<String>create(ordered);
    Multiset<String> sentSet = HashMultiset.<String>create(sent);
    if (orderedSet.equals(sentSet)) {
        return "No difference";
    } else {
        StringBuilder output = new StringBuilder();

        for (String item : Sets.union(orderedSet.elementSet(), sentSet.elementSet())) {
            int orderedCount = orderedSet.count(item);
            int sentCount = sentSet.count(item);

            if (orderedCount != sentCount) {
                if (output.length() > 0) {
                    output.append(" & ");
                }

                output.append(Math.abs(orderedCount - sentCount)).append(" item(s) missing in ");
                output.append(orderedCount > sentCount ? "sent" : "ordered").append(": ");
                output.append("\"").append(item).append("\"");
            }
        }
        return output.toString();
    }
}

如果由于某种原因您不能使用 Guava，那么您可以使用 Map<String， Integer 类型的 HashMap 实现与 HashMultiset 相同的行为>其中键是项目，值是原始列表中的出现次数（这是读者的练习）。

您的解决方案非常好，但还有一点改进的余地。

首先，您使用了 .大多数情况下，这是明智的，但这样做会遍历两个列表，直到找到第一个差异。这很糟糕，因为您不仅想知道这两个列表是否不同，还想知道这些差异是什么。这意味着，在遍历这些列表一次以确认存在差异之后，查找这些差异将需要再次遍历这两个列表，这会大大减慢解决方案的速度。.equals().equals()

取而代之的是，我将在这里做一个乐观的检查，只是为了处理有人在同一列表中通过的机会。我还使用 Objects.requireNonNull（object， message） 添加 null 检查。我还删除了你的 else 条款，而是提前返回。==

上述更改都不是真正必要的，但会消除简单的边缘情况。如果您觉得没有必要或不必要地使解决方案复杂化，请随时将它们排除在外。

(说到复杂性，一旦瓦尔哈拉出来，这个==可能就不再是一个好主意了。对于尚未推出的功能，我无法预测未来会有什么好建议，也不会有什么好建议，但把这个说明放在未来在后瓦尔哈拉世界中工作的读者）。

private static String getDifference(final List<String> list1, final List<String> list2)
{

    Objects.requireNonNull(list1, "list1 cannot be null");
    Objects.requireNonNull(list2, "list2 cannot be null");

    if (list1== list2)
    {
        return "No difference";
    } 

    //in progress

}

接下来，让我们找到一种快速方法来查找两者中缺失的元素。我不想对传入的任何一个列表进行任何破坏性的更改。另外，Java 有一些列表是不可修改的列表。一般来说，只复制你得到的东西，然后从那里开始，会更安全。

但请注意，如果合同中允许对传入列表进行破坏性更改，那么不制作副本会更有效率。无论如何，为了安全起见，我会复制一份。让我们现在就开始吧。

private static String getDifference(final List<String> list1, final List<String> list2)
{

    Objects.requireNonNull(list1, "list1 cannot be null");
    Objects.requireNonNull(list2, "list2 cannot be null");

    if (list1 == list2)
    {
        return "No difference";
    } 

    final List<String> copy1 = new ArrayList<>(list1);
    final List<String> copy2 = new ArrayList<>(list2);

    //in progress

}

好了，现在我们已经创建了副本，让我们删除两个列表共有的元素。为此，我们将使用 List.removeAll（） 方法。

private static String getDifference(final List<String> list1, final List<String> list2)
{

    Objects.requireNonNull(list1, "list1 cannot be null");
    Objects.requireNonNull(list2, "list2 cannot be null");

    if (list1 == list2)
    {
        return "No difference";
    } 

    final List<String> copy1 = new ArrayList<>(list1);
    final List<String> copy2 = new ArrayList<>(list2);

    //Yes, we are removing the OTHER SOURCE LIST from the COPY LIST
    copy1.removeAll(list2);
    copy2.removeAll(list1);

    //in progress

}

好的，我们现在发现了差异。剩下要做的就是返回结果。我将继续做一些基本的格式化，因为这对你来说似乎很重要。

private static String getDifference(final List<String> list1, final List<String> list2)
{

    Objects.requireNonNull(list1, "list1 cannot be null");
    Objects.requireNonNull(list2, "list2 cannot be null");

    if (list1 == list2)
    {
        return "No difference";
    } 

    final List<String> copy1 = new ArrayList<>(list1);
    final List<String> copy2 = new ArrayList<>(list2);

    //Yes, we are removing the OTHER SOURCE LIST from the COPY LIST
    copy1.removeAll(list2);
    copy2.removeAll(list1);

    if (copy1.isEmpty() && copy2.isEmpty())
    {
        return "No difference";
    }
    else if (copy1.isEmpty())
    {
        return "items missing in parameter 1 = " + copy2.toString();
    }
    else if (copy2.isEmpty())
    {
        return "items missing in parameter 2 = " + copy1.toString();
    }
    else
    {
        return "items missing in parameter 1 = " + copy2.toString() + " and items missing in parameter 2 = " + copy1.toString();
    }

}

这应该可以解决你的问题。下面是一些示例输出。

final List<String> list1 = List.of("A", "B", "C", "D");
final List<String> list2 = List.of("A", "B", "C", "E");
final List<String> list3 = List.of("A", "B", "C");

getDifference(list1, list1) // "No difference"
getDifference(list1, list2) // "items missing in parameter 1 = [E] and items missing in parameter 2 = [D]"
getDifference(list1, list3) // "items missing in parameter 2 = [D]"
getDifference(list2, list1) // "items missing in parameter 1 = [D] and items missing in parameter 2 = [E]"
getDifference(list2, list2) // "No difference"
getDifference(list2, list3) // "items missing in parameter 2 = [E]"
getDifference(list3, list1) // "items missing in parameter 1 = [D]"
getDifference(list3, list2) // "items missing in parameter 1 = [E]"
getDifference(list3, list3) // "No difference"

下面的代码循环访问这两个列表，同时更新两个包含差异的单独列表。我认为优点是您只迭代两个列表一次。但是，要使算法正常工作，必须对两个列表进行排序（按升序）。如果有一个前提条件，即始终对两个列表进行排序，则无需执行排序。例如，如果两个列表都包含数据库查询的结果，则存在这样的前提条件，因为每个查询都可以有一个 ORDER BY 子句。

代码后有更多解释。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    private static List<List<String>> diffs(List<String> lst1, List<String> lst2) {
        // For algorithm to work, both lists must be sorted.
        Collections.sort(lst1);
        Collections.sort(lst2);
        int ndx1 = 0;
        int ndx2 = 0;
        int size1 = lst1.size();
        int size2 = lst2.size();
        List<String> diffs1 = new ArrayList<>(size1); // strings in 'lst1' only
        List<String> diffs2 = new ArrayList<>(size2); // strings in 'lst2' only

        // Get first element in each list. Consider empty lists also.
        String str1 = size1 == 0 ? "" : lst1.get(ndx1);
        String str2 = size2 == 0 ? "" : lst2.get(ndx2);

        while (ndx1 < size1) {
            int difference = str1.compareTo(str2);
            // Always increment index of lower string
            if (difference > 0) {
                diffs2.add(str2);
                ndx2++;
                if (ndx2 < size2) {
                    str2 = lst2.get(ndx2);
                }
                else {
                    // if reach last element of 'lst2' add remaining elements of 'lst1'
                    while (ndx1 < size1) {
                        diffs1.add(lst1.get(ndx1++));
                    }
                    break;
                }
            }
            else if (difference < 0) {
                diffs1.add(str1);
                ndx1++;
                if (ndx1 < size1) {
                    str1 = lst1.get(ndx1);
                }
            }
            else {
                // strings are equal, increment both indexes
                ndx1++;
                if (ndx1 < size1) {
                    str1 = lst1.get(ndx1);
                }
                ndx2++;
                if (ndx2 < size2) {
                    str2 = lst2.get(ndx2);
                }
                else {
                    // if reach last element of 'lst2' add remaining elements of 'lst1'
                    while (ndx1 < size1) {
                        diffs1.add(lst1.get(ndx1++));
                    }
                    break;
                }
            }
        }
        // add remaining elements of 'lst2'
        while (ndx2 < size2) {
            diffs2.add(lst2.get(ndx2++));
        }
        return List.of(diffs1, diffs2);
    }

    private static void test(List<String> ordered, List<String> sent) {
        List<List<String>> diffs = diffs(ordered, sent);
        List<String> diffs0 = diffs.get(0);
        List<String> diffs1 = diffs.get(1);
        int count0 = diffs0.size();
        int count1 = diffs1.size();
        if (count0 == 0  &&  count1 == 0) {
            System.out.println("No differences.");
        }
        else {
            if (count1 > 0) {
                System.out.println("Missing in 'ordered': " + diffs1);
            }
            if (count0 > 0) {
                System.out.println("Missing in 'sent': " + diffs0);
            }
        }
        System.out.println("====================================================================");
    }

    public static void main(String[] args) {
        test(new ArrayList<>(List.of("A", "B")), new ArrayList<>(List.of("A", "B")));
        test(new ArrayList<>(List.of("A", "B", "C")), new ArrayList<>(List.of("B", "C")));
        test(new ArrayList<>(List.of("A", "D")), new ArrayList<>(List.of("A", "B", "C", "D")));
        test(new ArrayList<>(List.of("A", "D", "F")), new ArrayList<>(List.of("A", "B", "C", "D")));
    }
}

请注意，（in interface ）的方法已在JDK 9中添加。它创建一个不可变的列表，这意味着列表无法排序。因此，我将每个列表包装在一个可变列表中，该列表创建了一个可变列表，然后可以对其进行排序。java.util.ListArrayList

基本上，该算法的工作原理如下（假设两个列表都已排序）。

1. 获取两个列表的第一个元素。
2. 比较它们。
3. 如果它们不相等，则将较低的元素添加到其差异列表中，并获取包含较低元素的列表中的下一个元素。
4. 如果它们相等，则不向任何一个差异列表添加任何内容，并获取两个列表的下一个元素。
5. 迭代一个列表的所有元素后，将另一个列表的任何剩余元素添加到其差异列表中。
6. 第一个差异列表包含第一个列表中不在第二个列表中的所有元素，反之亦然。

这是我运行上述代码时得到的输出：

No differences.
====================================================================
Missing in 'sent': [A]
====================================================================
Missing in 'ordered': [B, C]
====================================================================
Missing in 'ordered': [B, C]
Missing in 'sent': [F]
====================================================================

用于查找不匹配的用户设置

import java.util.Collections;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.lang.String;
import java.util.*;



public class Main {

  

    public static void main(String[] args) {
        
         // Case 1
        List<String> order1 = Arrays.asList(new String[] { "A", "B" });
        List<String> sended1 = Arrays.asList(new String[] { "A", "B" });

        // No difference
        System.out.println("Case 1: " + getMissingItemsDescription(order1, sended1));

        // Case 2
        List<String> order2 = Arrays.asList(new String[] { "A", "B", "C" });
        List<String> sended2 = Arrays.asList(new String[] { "B", "C" });

        // "1 item(s) missing in sended: A"
        System.out.println("Case 2: " + getMissingItemsDescription(order2, sended2));

        // Case 3
        List<String> order3 = Arrays.asList(new String[] { "A", "D" });
        List<String> sended3 = Arrays.asList(new String[] { "A", "B", "C", "D" });

        // "2 item(s) missing in order: B, C"
        System.out.println("Case 3: " + getMissingItemsDescription(order3, sended3));

        // Case 4
        List<String> order4 = Arrays.asList(new String[] { "A", "D", "F" });
        List<String> sended4 = Arrays.asList(new String[] { "A", "B", "C", "D" });

        // 1 item(s) missing in sended: "F" & 2 item(s) missing in order: "B", "C"
        System.out.println("Case 4: " + getMissingItemsDescription(order4, sended4));


    }

      public static <T> String getMissingItemsDescription(List<T> order, List<T> sent) {
        Set<T> orderSet = new HashSet<>(order);
        Set<T> sentSet = new HashSet<>(sent);
        
        Set<T> missingInOrder = new HashSet<>(orderSet);
        missingInOrder.removeAll(sentSet);
        
        Set<T> missingInSent = new HashSet<>(sentSet);
        missingInSent.removeAll(orderSet);

        StringBuilder description = new StringBuilder();
        
        if (!missingInOrder.isEmpty()) {
            description.append("Missing in order: ").append(missingInOrder).append("\n");
        }
        
        if (!missingInSent.isEmpty()) {
            description.append("Missing in sent: ").append(missingInSent);
        }
        
        if (description.length() == 0) {
            description.append("No missing items found");
        }

        return description.toString();
    }
}

您可以使用 Java 8 Streams：

public static String differences(List<String> ordered, List<String> sent) {
    //look for ordered items missing in sent
    List<String> orderedButNotSent = ordered.stream()
        .filter(el -> sent.stream().noneMatch(el::equals))
        .collect(Collectors.toList());

    //look for sent items missing in ordered
    List<String> sentButNotOrdered = sent.stream()
        .filter(el -> ordered.stream().noneMatch(el::equals))
        .collect(Collectors.toList());

    //build report
    StringBuilder report = new StringBuilder();
    report.append("orderedButNotSent: " + orderedButNotSent + "\n")
          .append("sentButNotOrdered: " + sentButNotOrdered + "\n");

    //return report
    return report.toString();
}
public static void main(String args[]) {
    List<String> ordered = Arrays.asList(new String[] { "A", "D", "F" });
    List<String> sent = Arrays.asList(new String[] { "A", "B", "C", "D" });
    
    String differences = differences(ordered,sent);
    //=> orderedButNotSent: [F]
    //=> sentButNotOrdered: [B, C]
}

使用 Java 8 流：

这里的逻辑：

我使用了 java 8 操作来获得差异 在两个给定列表之间，并使用问题语句中提到的方法创建了输出消息。streamStringBuilder

法典：

public class Test {
    public static void main(String[] args) {
        // Case 1
        List<String> order1 = Arrays.asList("A", "B");
        List<String> sended1 = Arrays.asList("A", "B");
        System.out.println("Case 1: " + getMissingItems(order1,sended1));

        // Case 2
        List<String> order2 = Arrays.asList("A", "B", "C");
        List<String> sended2 = Arrays.asList("B", "C");
        System.out.println("Case 2: " + getMissingItems(order2,sended2));

        // Case 3
        List<String> order3 = Arrays.asList("A", "D");
        List<String> sended3 = Arrays.asList("A", "B", "C", "D");
        System.out.println("Case 3: " + getMissingItems(order3,sended3));

        // Case 4
        List<String> order4 = Arrays.asList("A", "D", "F");
        List<String> sended4 = Arrays.asList("A", "B", "C", "D");
        System.out.println("Case 4: " + getMissingItems(order4,sended4));
    }

    private static String getMissingItems(List<String> order, 
                                          List<String> sended){
        StringBuilder sb = new StringBuilder();
        List<String> missingInOrder = getMissingInList(order, sended);
        createMessage(sb, missingInOrder," item(s) missing in order: ");
        List<String> missingInSended = getMissingInList(sended, order);
        if(!missingInOrder.isEmpty() && !missingInSended.isEmpty()){
            sb.append(" && ");
        }
        createMessage(sb, missingInSended," item(s) missing in sended: ");
        return sb.isEmpty() ? "No difference":sb.toString();
    }

    private static void createMessage(StringBuilder sb, 
                                      List<String> diffInList,
                                      String msg) {
        if(!diffInList.isEmpty()){
            sb.append(diffInList.size())
              .append(msg)
              .append(String.join(",", diffInList));
        }
    }

    private static List<String> getMissingInList(List<String> list1, 
                                                 List<String> list2) {
        return list2.stream()
                    .filter(e -> !list1.contains(e))
                    .collect(Collectors.toList());
    }
}

输出：

Case 1: No difference
Case 2: 1 item(s) missing in sended: A
Case 3: 2 item(s) missing in order: B,C
Case 4: 2 item(s) missing in order: B,C && 1 item(s) missing in sended:F