检查一个数组是否是另一个数组的子集 - 特殊情况 [英] Check if one array is a subset of the other array - special case

问题描述

我正在研究一个初学者问题，该问题检查一个数组是否是另一个数组的子集，但我遇到了一个特殊情况，这是案例示例:a = [1,2,3], b = [1,1]，其中a包含1，b只包含1，但 b 不是 a 的子集，因为 b 包含两个 1>s.

I'm working on a beginner question that checks if one array is the subset of another array, and I got stuck on one special case, here is the case example: a = [1,2,3], b = [1,1], in which a contains 1, b only contains 1, but b is not a subset of a because b contains two of 1s.

如何修改我的代码以让它检查这种特殊情况?

How can I modify my code to have it check this special case?

以下是代码片段:

// True if one array is the subset of another array
public boolean checkSubset(int[] arr1, int[] arr2) {
    // A counter to remember how many
    // times the same element is found
    int cnt = 0;

    // If one of the array is empty, for empty set
    if (arr1.length == 0 || arr2.length == 0) {
        return true;
    }

    // Compare elements in two arrays
    for (int i = 0; i < arr1.length; ++i) {
        for (int j = 0; i < arr2.length; ++j) {
            if (arr1[i] == arr2[j]) {
                ++cnt;
                break;
            }
        }
    }

    // cnt would equal to the length of arr1 or arr2
    // if one array is the subset of the other one
    return (cnt == arr1.length || cnt == arr2.length);
}

推荐答案

你可以为两个数组实现一个自定义的泛型 containsAll 方法如下:

You can implement a custom generic containsAll method for two arrays as follows:

/**
 * @param a   first array.
 * @param b   second array.
 * @param <T> type of array elements.
 * @return whether the first array contains
 * all the elements from the second array.
 */
public static <T> boolean containsAll(T[] a, T[] b) {
    // incorrect incoming data
    if (a == null || b == null) return false;
    // copy of the first array
    T[] c = Arrays.copyOf(a, a.length);
    // iterate through the second array and remove its
    // elements from the copy of the first array, if any
    for (T e : b)
        // iterate through the copy of the first array
        for (int i = 0; i < c.length; i++)
            // this element is equal to the
            // element from the second array
            if (c[i] != null && c[i].equals(e)) {
                // shift the subsequent elements back
                System.arraycopy(c, i + 1, c, i, c.length - i - 1);
                // truncate the array by one element
                c = Arrays.copyOf(c, c.length - 1);
                // exit the inner loop
                break;
            }
    // return whether the size of the first array
    // is equal to the size of the second array plus
    // what is left in the copy of the first array
    return a.length == b.length + c.length;
}

public static void main(String[] args) {
    Integer[] a = {1, 2, 3, 1};
    Integer[] b = {1, 1};
    boolean isSubset = containsAll(a, b);
    System.out.println(isSubset); // true
}

这篇关于检查一个数组是否是另一个数组的子集 - 特殊情况的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！