Как проверить, является ли список подмножеством другого списка

Question

list1:[1,2,3,4,5] 
list2:[1,2,3] 

Как проверить, является ли list2 подмножеством списка1? Я попробовал containsAll(), но он возвращает true, пока элементы в списке 2 присутствуют в списке1. Мне нужен тот же порядок, что и критерии, а не только элементы.

Answer 1

Вот алгоритм

1) перебрать второй список

2) Проверьте, если элемент содержится в первом списке

если нет возврата ложного

Если да, получить индекс этого элемента из первого списка, используя indexOf()

3) Теперь, когда итерация проверяет, равен ли следующий элемент списку1 (LastMatchedIndexFromList1 ++)

если вернуть ложные

если да повторите шаг 3 и возвращает истину в конце итерации

Answer 2

Я немного любопытно о реализации этого, так что это мое решение:

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

}

Answer 3

Итерация list2, чтобы проверить, существует ли каждый элемент в list1. Самый простой способ - использовать indexOf для выполнения операции проверки, он возвращает индекс первого вхождения указанного элемента в этом списке или -1, если этот список не содержит этот элемент. Каждая сложность времени проверки проверки равна O(n), поскольку в худшем случае она должна перебирать весь список.

В то время, если заказано list1, мы можем использовать BinarySearch, чтобы улучшить производительность проверки до O(lgn).

Пример код здесь:

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

время сложность O(n * m), что n является 'размером s и m является list2' list1 s размера.

Но, самый эффективный способ не использовать indexOf способ сделать проверку. Так как требуется порядок вхождения, нет никакой необходимости итерации целого list1 в каждой операции проверки. Просто с последнего индекса контрольной точки, чтобы сделать проверку!

Пример кода здесь:

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

Оба list1 и list2 повторяются только один раз, время сложность O(n + m).

Answer 4

Используйте это:

boolean contains(List<?> list, List<?> sublist) { 
    return Collections.indexOfSubList(list, sublist) != -1; 
    } 

http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#indexOfSubList(java.util.List,%20java.util.List)

Answer 5

Я попытался ниже код для нахождения элементов в порядке

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