检查数组列表是否为子集时如何处理多重性

Question

我有两个 Arraylist，我想检查一个是否是另一个的子集（顺序在比较中并不重要）。问题是：假设 Ar1={e,e,r} 和 Ar2={e,r,b,d}。在我的代码中它说 Ar1 是一个子集。但我想让它说 false，因为 Ar2 只有一个 e。怎么做？

public static void dostuff(String word1,String word2){
    List<String> list1 = new ArrayList<String>();
    List<String> list2 = new ArrayList<String>();

    for (String character : word1.split("")) {
        list1.add(character);
    }
    for (String character : word2.split("")) {
        list2.add(character);
    }

    boolean sub = list1.containsAll(list2) || list2.containsAll(list1);

    System.out.println(sub);
}

Answer 1

这是一个可行的解决方案

勾选Demo

 public static void main (String[] args) throws java.lang.Exception
 {
    dostuff("eer","erbd");
 }

 public static void dostuff(String word1, String word2) {
        List<String> list1 = new ArrayList<String>();

   for (String character : word1.split("")) {
            list1.add(character);
        }

        boolean sub = true;
        for (String character : word2.split("")) {
            if (list1.remove(character)) {
               if (list1.isEmpty()) {
                    break;
                }
            } else {
                sub = false;
                break;
            }
        }
        System.out.println(sub);
    }

Answer 2

另请注意，数学集 java 是唯一的，因此请小心使用术语 "subset"。

您可以使用频率图来测试是否有一个列表 "has each element in another list, with the same or fewer occurrences"。也就是说，一旦你有了列表，你就可以将它转换成 Map<T, Integer> 来存储每个列表元素的计数。使用 map 避免改变原始列表（如果在遇到它们时通过从主列表中删除元素进行测试，您会这样做）：

public static <T> boolean isSublist(List<T> masterList, List<T> subList) {
    Map<T, Integer> masterMap = new HashMap<T, Integer>();
    for (T t : masterList) masterMap.put(t, 1 + masterMap.getOrDefault(t, 0));

    Map<T, Integer> testMap = new HashMap<T, Integer>();
    for (T t : subList) testMap.put(t, 1 + testMap.getOrDefault(t, 0));

    for(Map.Entry<T, Integer> entry : testMap.entrySet()) {
        if (masterMap.getOrDefault(entry.getKey(), 0) < entry.getValue()) return false;
    }

    return true;
}

getOrDefault 仅从 Java 8 开始可用，但您可以轻松编写自己的方法来处理相同的操作。

Answer 3

我想这可能就是您想要的。请注意 list2.remove(elem) returns true 如果一个元素被删除， false 如果没有。

public static boolean dostuff(String word1,String word2){
    List<String> list1 = new ArrayList<>();
    List<String> list2 = new ArrayList<>();
    List<String> list3;

    for (String character : word1.split("")) {
        list1.add(character);
    }

    for (String character : word2.split("")) {
        list2.add(character);
    }

    list3 = new ArrayList<>(list2);

    boolean isSubset = true;

    for (final String elem : list1) {
        if (!list2.remove(elem)) {
            isSubset = false;
            break;
        }
    }

    if (isSubset) {
        return true;
    }

    for (final String elem : list3) {
        if (!list1.remove(elem)) {
            return false;
        }
    }

    return true;
}

Answer 4

@Johdoe。以下逻辑可能对您有所帮助。你可以根据需要进行优化。

ArrayList<String> list1 = new ArrayList<String>();
ArrayList<String> list2 = new ArrayList<String>();
list1.add("e");
list1.add("a");
list1.add("r");

list2.add("e");
list2.add("r");
list2.add("b");
list2.add("d");
list2.add("a");
System.out.println("list2 " + list2);
System.out.println("list1 " + list1);

Set<Integer> tempList = new HashSet<Integer>();

System.out.println("  containsAll " + list2.containsAll(list1));
for (int i = 0; i < list2.size(); i++) {
    for (int j = 0; j < list1.size(); j++) {
        if (list2.get(i).equals(list1.get(j))) {
            tempList.add(i);
        }
    }
}
System.out.println(" tempList  " + tempList);
System.out.println("list 1 is subset of list 2  "
        + (tempList.size() == list1.size()));

Answer 5

现在我明白了内容的顺序并不重要，您只想知道一个字符串的所有字符是否存在于另一个字符串中（频率相同），反之亦然。

试试这个函数，它会检查所有内容，而无需调用该方法两次，也无需使用流：

public static boolean subsetExists(String s1, String s2) {
    String temp = s2.replaceAll(String.format("[^%s]", s1), "");
    char[] arr1 = s1.toCharArray();
    char[] arr2 = temp.toCharArray();
    Arrays.sort(arr1);
    Arrays.sort(arr2);

    boolean isSubset = new String(arr2).contains(new String(arr1));
    if (!isSubset) {
        temp = s1.replaceAll(String.format("[^%s]", s2), "");
        arr1 = temp.toCharArray();
        arr2 = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);

        isSubset = new String(arr1).contains(new String(arr2));
    }
    return isSubset;
}

您不必费心将 String 变成 List。发生的事情是我们正在检查 s1 中的所有字母是否都存在于 s2 中，反之亦然。

我们从 s2 中删除了不在 s1 中的字符，并将结果存储在临时 String 中。将临时 String 和 s1 都转换为 char[]。然后我们对两个数组进行排序并将它们转换回 Strings。然后我们可以检查 NEW SORTED 临时 String contains() NEW SORTED s1。如果此结果为假，则我们应用从 s2 到 s1.

的相同逻辑检查

用法：

public static void main(String[] args) throws Exception {
    String s1 = "eer";
    String s2 = "bderz";
    String s3 = "bderzzeee";

    System.out.println(subsetExists(s1, s2));
    System.out.println(subsetExists(s1, s3));
}

public static boolean subsetExists(String s1, String s2) {
    String temp = s2.replaceAll(String.format("[^%s]", s1), "");
    char[] arr1 = s1.toCharArray();
    char[] arr2 = temp.toCharArray();
    Arrays.sort(arr1);
    Arrays.sort(arr2);

    boolean isSubset = new String(arr2).contains(new String(arr1));
    if (!isSubset) {
        temp = s1.replaceAll(String.format("[^%s]", s2), "");
        arr1 = temp.toCharArray();
        arr2 = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);

        isSubset = new String(arr1).contains(new String(arr2));
    }
    return isSubset;
}

结果：

false
true

Answer 6

我自己找到了解决方法，请检查是否正确，但我相信是。

public static void dostuff(String word1, String word2) {
    boolean sub = false;

    ArrayList<String> list1 = new ArrayList<String>();
    ArrayList<String> list2 = new ArrayList<String>();
    ArrayList<String> list3 = new ArrayList<String>();
    for (int i = 0; i < word1.length(); i++) {
        list1.add(word1.split("")[i]);
    }
    for (int i = 0; i < word2.length(); i++) {
        list2.add(word2.split("")[i]);
    }

    if (list1.size() >= list2.size()) {
        for (String i : list2) {
            if (list1.contains(i)) {
                list1.remove(i);
                list3.add(i);
            }
        }
        if (list2.containsAll(list3) && list2.size() == list3.size()) {
            sub = true;
        }
    } else if (list2.size() > list1.size()) {
        for (String i : list1) {
            if (list2.contains(i)) {
                list2.remove(i);
                list3.add(i);
            }
            if (list1.containsAll(list3) && list1.size() == list3.size()) {
                sub = true;
            }
        }
    }
    System.out.println(sub);
}

Answer 7

您可以使用几个映射来存储每个字母的频率：

public static void dostuff(String word1, String word2) {
    Map<String, Long> freq1 = Arrays.stream(word1.split("")).collect(
        Collectors.groupingBy(Function.identity(), Collectors.counting()));

    Map<String, Long> freq2 = Arrays.stream(word2.split("")).collect(
        Collectors.groupingBy(Function.identity(), Collectors.counting()));

    System.out.println(contains(freq1, freq2) || contains(freq2, freq1));
}

其中 contains 方法如下：

private static boolean contains(Map<String, Long> freq1, Map<String, Long> freq2) {
    return freq1.entrySet().stream().allMatch(
        e1 -> e1.getValue().equals(freq2.get(e1.getKey())));
}

测试：

dostuff("eer", "erbd"); // {r=1, e=2}, {b=1, r=1, d=1, e=1}, false

dostuff("erbed", "eer"); // {b=1, r=1, d=1, e=2}, {r=1, e=2}, true

想法是使用 java 8 个流来创建频率映射，然后流式传输两个映射的条目集以比较所有元素及其频率。如果所有条目都匹配，则意味着第二个列表包含第一个列表中具有相同频率的所有元素，无论顺序如何。

如果第一个列表的结果是 false，则根据问题要求，也会以相反的方式执行检查。

检查数组列表是否为子集时如何处理多重性

How to deal with multiplicity when checking if an arraylist is a subset

java

arraylist

subset

multiplicity