如何检查一个列表是否是 java 中另一个列表的子集？

Question

我正在尝试检查一个列表是否是 java 中另一个列表的子集。我使用 for 循环来检查元素，并且我有一个名为 same 的变量，每次元素相同时该变量都会递增。问题是列表 returns 仅当元素处于相同位置

时才为真

例如：

(0,1) (0,1,2,3 ) true
(1,0) (0,1,2,3) false

我写了下面的代码：

public Boolean contains(ItemsList ilist) {
    int same = 0;

    if (empty()) {
        return false;
    } else {
        ItemNode a = this.first;
        ItemNode b = ilist.first;

        for (b = ilist.first; b != null; b = b.next) {
            for (a = this.first; a != null; a = a.next) {
                if (a.item == b.item) {
                    same++;
                }
            }
        }
    }

    return (same > 0);
}

Answer 1

解决这个问题的方法与解决子串匹配问题非常相似。

您首先检查 假定的子集列表 的第一个元素（此后称为 SSL）。

一旦找到匹配项，记下索引（此后将在找到匹配项的主列表中称为 myGuy，继续检查后续元素是否SSL 匹配主列表。

如果你的比赛已经完成，那么只需 return。如果没有，那么您可以执行两者之一。如果主列表有剩余元素，则递增 myGuy 然后它成为您在主列表中开始迭代的新索引。
如果没有留下任何元素并且仍然没有完全匹配那么它不是一个子集。

以下是您在 Java 中的操作方法：

private static boolean checkSubList(int[] mainList, int[] subList) {
    int currentIteratingPointer;
    int matchCounter = 0;

    for (int i = 0; i < mainList.length; i++) {
        currentIteratingPointer = i;
        for (int j = 0; j < subList.length; j++) {
            if (mainList[currentIteratingPointer] == subList[j]) {
                System.out.println(mainList[currentIteratingPointer]);
                ++matchCounter;
                ++currentIteratingPointer;
            } else {
                --matchCounter;
                break;
            }
        }

        i = currentIteratingPointer;
    }

    return matchCounter == subList.length; // You can count the number of occurance of the sublist if you change
    // it to int and return the matchCounter a
}

Answer 2

试试这个来源

public class ListTest {

    List small = new ArrayList<>();
    List big = new ArrayList<>();

    public static void main(String args[]) {
        ListTest g = new ListTest();

        g.populateList();
        boolean bFlag = g.checkIfSubset();
        System.out.println("====is subset====>" + bFlag);
    }

    private boolean checkIfSubset() {
        for (Object in : small) {
            if (!big.contains(in)) {
                return false;
            }
        }
        return true;
    }

    private void populateList() {
        small.add(11);
        small.add(23);

        big.add(11);
        big.add(2);
        big.add(23);
        big.add(24);
    }

}

Answer 3

问题是 contains 对于 Set 会很好（对于唯一数字），但是对于 List 一个天真的 contains 需要两个嵌套循环，二次复杂度 O(N²) ：两个包含 100 个元素的列表需要 10,000 个步骤。因此，应该将列表转换为集合，或者 sort 列表。

列表排序可能是 O(N log N)，但对于您似乎拥有的链表，它保持不变：

public ItemsList sort(ItemsList list) {
    ItemsList sortedList = new ItemsList();
    for (ItemNode node : list) {
        sortedList.insertSorted(node.item);
    }
    return sortedList;
}

但是排序后你可以按照你说的去做，线性复杂度为O(N)。

public boolean contains(ItemsList ilist) {
    ItemsList sortedThis = this.sorted();
    ItemsList sortedOther = iList.sorted();
    ItemNode node = sortedThis.first;
    ItemNode other = otherList.first;
    while (node != null) {
        if (other == null) {
            break; // return true;
        }
        if (other.item < node.item) {
            break; // return false;
        }
        if (other.item == node.item) {
            other = other.next; // Match found.
        }
        node = node.next;
    }
    return other == null;
}

由于列表可能包含重复项，因此请进行排序。

Answer 4

所以基本上你想在另一个列表中找到一个字谜。

这是我对字符串字谜的实现

abcde, dbc -> 真

检查我的代码并尝试在您的用例中实现它。

public boolean findStringAnagrams(String str, String pattern) {


        Map<Character, Integer> charMap = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            charMap.put(pattern.charAt(i), charMap.getOrDefault(pattern.charAt(i), 0) + 1);
        }

        Integer windowStart = pattern.length() - 1;
        for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {

            Character c = str.charAt(windowEnd);
            charMap.computeIfPresent(c, (key, val) -> val - 1);
            if (charMap.containsKey(c) && charMap.get(c) == 0)
                charMap.remove(c);

            if (windowStart < windowEnd) {

                if (charMap.size() == 0) {
                    return true;
                }
                charMap.put(str.charAt(windowStart), charMap.getOrDefault(str.charAt(windowStart), 0) + 1);
                windowStart++;
            }

        }

        return false;
    }

Answer 5

请注意，似乎 Collections.indexOfSubList 可能不适用于字符串？这种方法有效，使用 Apache Commons 集合

  import org.apache.commons.collections.CollectionUtils;
  import static org.junit.jupiter.api.Assertions.assertEquals;
  import java.util.List;
  import java.util.Map;
  import java.util.stream.Collectors;

  private static boolean isSublistOfList(List list, List sublist) {
    List dedupedSublist = (List) sublist.stream().distinct().collect(Collectors.toList());

    boolean result = CollectionUtils.isSubCollection(dedupedSublist, list);

    return result;
  }

  @Test
  void testIt(){
    List<String> parentDataList = List.of("this", "is", "a", "test", "string", "and", "a", "test", "other");
    List<String> child1 = List.of("a", "test");
    List<String> child2 = List.of("this", "string");
    List<String> child3 = List.of("is", "not", "test");
    List<String> child4 = List.of("string", "this", "this");
    assertEquals(true, isSublistOfList(parentDataList, child1));
    assertEquals(true, isSublistOfList(parentDataList, child2));
    assertEquals(false, isSublistOfList(parentDataList, child3));
    assertEquals(true, isSublistOfList(parentDataList, child4));

    List<Integer> parentList1 = List.of(1,2,3,4,5);
    List<Integer> subList1 = List.of(4);
    List<Integer> subList2 = List.of(5,4,3,2,2,1);
    List<Integer> subList3 = List.of(5,6);
    List<Integer> subList4 = List.of();
    assertEquals(true, isSublistOfList(parentList1, subList1));
    assertEquals(true, isSublistOfList(parentList1, subList2));
    assertEquals(false, isSublistOfList(parentList1, subList3));
    assertEquals(true, isSublistOfList(parentList1, subList4));
  }

Answer 6

def isSubset(l,s):  
    if len(s) > len(l):  
        return False  
    elif s == l:  
        return True  
    elif len(s) <= 0:    
        return True  
    else:  
       for i in range(len(l)):  
           if l[i] == s[0]:   
               n = 1  
               while n < len(s) and l[i+n] == s[n]:  
                    n += 1  
               if n == len(s):  
                   return True

Answer 7

尝试：

list1.containsAll(list2);

如果 list2 是 list1 的子集，这将 return 一个 'True'，否则 return 'False'

Reference

如何检查一个列表是否是 java 中另一个列表的子集？

How to check if a list is a subset of another list in java?

java

algorithm

list

comparison

element