An array is subset of another array

问题:

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.

回答1:

Make a HashSet out 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.

回答2:

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

boolean isSubset = bigList.containsAll(smallList);

This will do exactly what you want, efficiently.

回答3:

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

回答4:

I have came with two different solution

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

• first solution iterates over both arrays and compare, main[i] = -1 is 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....9 and value as 0,
  next we iterate over main array and +1 to respective value
  next we iterate over sub array and -1 to 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);
  }
  

回答5:

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.

boolean 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){

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;

}

回答6:

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

If not use hasmap as someone already suggested.

回答7:

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