java 一个数组是另一个数组的子集

An array is subset of another array

提问by MTT

How can I efficiently check to see whether all the elements in an integer array are subset of all elements of another Array in java? For example [33 11 23] is subset of [11 23 33 42]. Thanks in advance.

如何有效地检查整数数组中的所有元素是否是java中另一个数组的所有元素的子集？例如 [33 11 23] 是 [11 23 33 42] 的子集。提前致谢。

回答by Matt Wielbut

If you're not bound to using Arrays, any Java collection has the containsAllmethod:

如果您不绑定使用数组，则任何 Java 集合都具有以下containsAll方法：

boolean isSubset = bigList.containsAll(smallList);

This will do exactly what you want, efficiently.

这将完全有效地执行您想要的操作。

回答by marcadian

assume you want to check A is subset of B. put each element of B into a hash, then iterate over elements in A, all of them must exist in the hash

假设您要检查 A 是 B 的子集。将 B 的每个元素放入一个散列中，然后遍历 A 中的元素，它们都必须存在于散列中

回答by Patashu

Make a HashSetout of the superset array. Check if each of the elements of the subset array are contained in the HashSet. This is a very fast operation.

做HashSet出来的超阵。检查子集数组的每个元素是否包含在HashSet. 这是一个非常快的操作。

回答by Ban

The outer loop picks all the elements of arr2[] one by one. The inner loop linearly searches for the element picked by outer loop. If all elements are found then return true, else return false.

外循环将 arr2[] 的所有元素一一选取。内循环线性搜索外循环选取的元素。如果找到所有元素，则返回 true ，否则返回 false。

boolean checkIsSubset(int arr1[], int arr2[]){

布尔值 checkIsSubset(int arr1[], int arr2[]){

    int m=arr1.length,  n=arr2.length;
    int i = 0;
    int j = 0;
    for (i=0; i<n; i++){
        for (j = 0; j<m; j++){
           if(arr2[i] == arr1[j])
              break;
        }
        if (j == m)
           return false;
    }
    return true;
}

Why do binary search after sorting?? Since both arrays will be available in sorted form, we can just use two pointers as follows:-

为什么排序后要二分查找？？由于两个数组都以排序形式提供，我们可以只使用两个指针，如下所示：-

boolean isSubset(int arr1[], int arr2[], int m, int n){

boolean isSubset(int arr1[], int arr2[], int m, int n){

int i = 0, j = 0;
quickSort(arr1, 0, m-1);
quickSort(arr2, 0, n-1);
while( i < n && j < m )
{
    if( arr1[j] <arr2[i] )
        j++;
    else if( arr1[j] == arr2[i] )
    {
        j++;
        i++;
    }
    else if( arr1[j] > arr2[i] )
        return false;
}

if( i < n )
    return false;
else
    return true;

}

}

回答by ericdemo07

I have came with two different solution

我带来了两种不同的解决方案

input: int mainArray[] = { 1, 2, 3, 2, 5, 6, 2 }, subArray[] = { 2, 2, 2 };

输入： int mainArray[] = { 1, 2, 3, 2, 5, 6, 2 }, subArray[] = { 2, 2, 2 };

• first solution iterates over both arrays and compare, main[i] = -1is used to avoid repeating elements included again

  void findIfArrayIsASubset(int[] main, int[] sub) {
  int count = 0;
  for (int i = 0; i < main.length; i++) {
      for (int j = 0; j < sub.length; j++) {
          if (main[i] == sub[j]) {
              main[i] = -1;
              count++;
              break;
          }
      }
  }
  if (count == sub.length)
      System.out.println("is a subset");
  else
      System.out.println("is not a subset");
  }
  

• second solution uses hashmap having keys from 1....9and value as 0,
  next we iterate over main array and +1to respective value
  next we iterate over sub array and -1to respective value
  next comapre sum of values of hashmap to difference in length of two array

  void findIfArrayIsASubset(int[] main, int[] sub) {
  Map<Integer, Integer> mainMap = new HashMap<Integer, Integer>();
  for (int i = 0; i < 10; i++) {
      mainMap.put(i, 0);
  }
  for (int i = 0; i < main.length; i++) {
      mainMap.put(main[i], mainMap.get(main[i]) + 1);
  }
  for (int i = 0; i < sub.length; i++) {
      mainMap.put(main[i], mainMap.get(main[i]) - 1);
  }
  String output = mainMap.values().stream().reduce(0, Integer::sum).compareTo(main.length - sub.length) == 0
          ? "is a subset" : "not a subset";
  System.out.println(output);
  }
  

• 第一个解决方案迭代两个数组并进行比较， main[i] = -1用于避免重复包含的元素

  void findIfArrayIsASubset(int[] main, int[] sub) {
  int count = 0;
  for (int i = 0; i < main.length; i++) {
      for (int j = 0; j < sub.length; j++) {
          if (main[i] == sub[j]) {
              main[i] = -1;
              count++;
              break;
          }
      }
  }
  if (count == sub.length)
      System.out.println("is a subset");
  else
      System.out.println("is not a subset");
  }
  

• 第二种解决方案使用具有键 from1....9和 value as 的hashmap 0，
  接下来我们遍历主数组和+1相应的值，
  接下来我们遍历子数组和-1相应的值，
  下一个将 hashmap 的值相加到两个数组的长度差

  void findIfArrayIsASubset(int[] main, int[] sub) {
  Map<Integer, Integer> mainMap = new HashMap<Integer, Integer>();
  for (int i = 0; i < 10; i++) {
      mainMap.put(i, 0);
  }
  for (int i = 0; i < main.length; i++) {
      mainMap.put(main[i], mainMap.get(main[i]) + 1);
  }
  for (int i = 0; i < sub.length; i++) {
      mainMap.put(main[i], mainMap.get(main[i]) - 1);
  }
  String output = mainMap.values().stream().reduce(0, Integer::sum).compareTo(main.length - sub.length) == 0
          ? "is a subset" : "not a subset";
  System.out.println(output);
  }
  

回答by David Prun

Sort both the arrays and check all the elements in smaller array are present in larget array. This is without using extra space.

对两个数组进行排序并检查较小数组中的所有元素是否存在于 larget 数组中。这是不使用额外空间的。

If not use hasmap as someone already suggested.

如果不使用已经有人建议的 hasmap 。

回答by Evgeniy Dorofeev

This checks if any elements of the possible subset is missing from the larger array. If it is, it's not a subset:

这会检查较大数组中是否缺少可能子集的任何元素。如果是，则它不是子集：

boolean isSubset(int[] a1, int[] a2) {
    a2 = Arrays.copyOf(a2, a2.length);
    Arrays.sort(a2);
    for(int e : a1) {
        if (Arrays.binarySearch(a2, e) < 0) {
            return false;
        }
    }
    return true;
}