英文:
Compare two list and output missing and extra element in Java
问题
我有两个字符串列表 List A 和 B。列表的长度可能相同，也可能一个比另一个长。每个列表中没有重复值。它们由随机数组成。
我想要做的是找出 A 中相对于列表 B 而言缺失的元素和多余的元素。然后将它们保存在两个新的列表中，一个用于缺失元素，另一个用于多余元素。
例如：
A = ["3000047", "3000042", "3000030", "30000475"]
B = ["3000047", "3000043", "3000030"]
输出应该为：
缺失元素 = ["3000043"]
多余元素 = ["3000042", "30000475"]
我考虑采取以下步骤。但不确定其性能和效率。
1. 从 A 中读取元素。
2. 检查元素是否存在于 B 中。
3. 如果不存在，则将其添加到多余元素列表。
4. 如果存在，则从 A 和 B 中都删除该元素。
5. 如果 B 为空，则将所有剩余元素添加到多余元素列表。
6. 如果 A 为空，则将所有剩余元素添加到缺失元素列表。
英文:
I have two lists of strings List A and B.Lists might have same length or maybe one is longer than the other.There's no duplicate values in each list.They consist of random numbers.
What I want to do is to find the missing and the extra element exists in A compared to list B.And save them in two new lists , one for missing elements and one for extra elements.
For Example :
A = ["3000047" , "3000042" , "3000030" , "30000475"]
B = ["3000047" , "3000043" , "3000030" ]
The output should be
Missing = ["3000043"]
Extra = ["3000042" , "30000475"]
I think of doing at as below. But not sure about the performance and its efficiency.
- Read element from A.
- Check if element exists in B.
- If no add it to Extra list.
- If yes remove the element from both A and B.
- If B is empty add all renaming elements in Extra list.
- If A is empty add all renaming elements in Missing list.
答案1
得分: 8
> 但不确定性能和效率方面的情况。
就性能而言，使用Set（HashSet实现）而不是List。这将在以下情况下给出更好的O时间复杂度：
> 2. 检查元素是否存在于 B 中。
这是您将应用contains方法的时候。详细信息请参阅这个答案。
> 对于HashSet的contains是O(1)，而对于列表来说是O(n)，因此如果您经常需要运行contains，则永远不应该使用列表。
您提出的算法可以使用Java内置函数实现。
Set#removeAll
Set<String> A = new HashSet<>(Arrays.asList("3000047", "3000042", "3000030", "30000475"));
Set<String> B = new HashSet<>(Arrays.asList("3000047", "3000043", "3000030"));
Set<String> copyA = new HashSet<>(A);
Set<String> copyB = new HashSet<>(B);
copyB.removeAll(A);
System.out.println("Missing: " + copyB);
copyA.removeAll(B);
System.out.println("Extra: " + copyA);
Output
Missing: [3000043]
Extra: [3000042, 30000475]
英文:
> But not sure about the performance and its efficiency
Performance wise, use Set (HashSet implementation) instead of List. This will give better O time complexity at:
> 2. Check if element exists in B.
This is when you'll apply contains method. Check this answer for details on that.
> Contains for a HashSet is O(1) compared to O(n) for a list, therefore you should never use a list if you often need to run contains.
The algorithm that you've proposed could be achieved using Java built-in functions.
Set#removeAll
Set<String> A = new HashSet<>(Arrays.asList("3000047", "3000042", "3000030", "30000475"));
Set<String> B = new HashSet<>(Arrays.asList("3000047", "3000043", "3000030"));
Set<String> copyA = new HashSet<>(A);
Set<String> copyB = new HashSet<>(B);
copyB.removeAll(A);
System.out.println("Missing: " + copyB);
copyA.removeAll(B);
System.out.println("Extra: " + copyA);
Output
Missing: [3000043]
Extra: [3000042, 30000475]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论