java 如何检查一个列表是否是另一个列表的子集
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/29862577/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to check whether a list is a subset of another list
提问by Zaq
list1:[1,2,3,4,5]
list2:[1,2,3]
How to check if list2 is a subset of list1? I tried containsAll() but it gives true as long as the elements in list 2 are present in list1. I want the same order as criteria and not just the elements.
如何检查list2是否是list1的子集？我尝试了 containsAll() 但只要列表 2 中的元素存在于列表 1 中，它就会给出 true。我想要与标准相同的顺序，而不仅仅是元素。
回答by Laszlo Hirdi
Use this:
用这个：
boolean contains(List<?> list, List<?> sublist) {
return Collections.indexOfSubList(list, sublist) != -1;
}
回答by M Sach
Here is the Algorithm
这是算法
1) Iterate over second list
1) 迭代第二个列表
2) Check if element is contained in first list
2) 检查元素是否包含在第一个列表中
if no return false
如果没有返回假
If yes, get the index of that element from first list using indexOf()
如果是，则使用indexOf()从第一个列表中获取该元素的索引
3) Now while iterating check if next element is equal to list1(lastMatchedIndexFromList1++)
3) 现在在迭代时检查下一个元素是否等于 list1(lastMatchedIndexFromList1++)
if return false
如果返回假
if yes repeat step 3 and return true at end of iteration
如果是，重复步骤 3 并在迭代结束时返回 true
回答by jbarrueta
I got a little curious about the implementation of this so this is my solution:
我对这个的实现有点好奇所以这是我的解决方案：
public static void main(String[] args) {
List<Integer> list1 = new ArrayList<>();
list1.add(1);
list1.add(2);
list1.add(3);
list1.add(4);
list1.add(5);
List<Integer> list2 = new ArrayList<>();
list2.add(1);
list2.add(2);
list2.add(3);
boolean isOrderedSublist = true;
for (int i = 0; i < list2.size(); i++) {
if(list1.get(i) != (int) list2.get(i)) {
isOrderedSublist = false;
break;
}
}
System.out.println("Is ordered: " + isOrderedSublist);
}
}
}
回答by coderz
Iterate list2to check whether each element exists in list1. The most simple way is to use indexOfto do check operation, it returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. Each check operation time complexity is O(n)because it has to iterate the whole list in worst case.
迭代list2检查每个元素是否存在于list1. 最简单的方法是使用indexOf做检查操作，它返回指定元素在这个列表中第一次出现的索引，如果这个列表不包含该元素，则返回-1。每个检查操作的时间复杂度是O(n)因为它在最坏的情况下必须迭代整个列表。
While if the list1is ordered, we can use BinarySearchto improve check operation performance to O(lgn)time complexity.
而如果list1是有序的，我们可以使用BinarySearch将检查操作性能提高到O(lgn)时间复杂度。
Sample code here:
示例代码在这里：
List<Integer> list1 = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
List<Integer> list2 = new ArrayList<>(Arrays.asList(1, 2, 5));
boolean contains = true;
int l2 = list2.size();
int currIndex = -1;
for(int j=0;j<l2;j++) {
int e2 = list2.get(j);
int i1 = list1.indexOf(e2);
if(i1 == -1) {
contains = false;
break;
}
if(i1 > currIndex) {
currIndex = i1;
}
}
System.out.println(contains);
The time complexity is O(n * m), which nis list1's size and mis list2's size.
时间复杂度为O(n * m)，这n是list1的规模和m是list2的大小。
But, the most efficient way is not to use indexOfmethod to do check. Since the occurence order is required, there is no need to iterate whole list1in each check operation. Just from last check point index to do checking!
但是，最有效的方法是不要使用indexOf方法进行检查。由于需要出现顺序，因此不需要list1在每个检查操作中迭代整个。只是从上次检查点索引做检查！
Sample code here:
示例代码在这里：
boolean contains = true;
int l1 = list1.size(), l2 = list2.size();
int currIndex = 0;
int i;
for(int j=0;j<l2;j++) {
int e2 = list2.get(j);
for(i=currIndex;i<l1;i++) {
if(e2 == list1.get(i)) {
break;
}
}
if(i == l1) {
contains = false;
break;
}
currIndex++;
}
System.out.println(contains);
Both list1and list2are iterated just once, the time complexity is O(n + m).
这两个list1和list2被重复只有一次，时间复杂度为O(n + m)。
回答by Naveenkumar Chinnakalappa
I tried below code for finding the elements in the order
我尝试了下面的代码来按顺序查找元素
import java.util.List;
import java.util.ArrayList;
class OrderArray {
public static void main(String [] args) {
List listSource = new ArrayList();
for(int i =1; i <=5; i++) {
listSource.add(i);
}
List target = new ArrayList();
target.add(2);
target.add(3);
boolean isMatched = true;
int [] indexArray = new int[target.size()];
for(int i = 0; i< target.size(); i ++) {
indexArray[i] = listSource.indexOf(target.get(i));
if ( i !=0 ) {
if ((indexArray[i] - indexArray[i-1]) != 1) {
isMatched = false;
break;
}
}
}
System.out.println("isMatched:"+isMatched);
}
}
