3

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

4

7 回答 7

9

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

boolean isSubset = bigList.containsAll(smallList);

这将有效地完成您想要的工作。

于 2013-03-26T03:12:13.280 回答
3

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

于 2013-03-26T03:06:29.933 回答
3

HashSet从超集数组中创建一个。检查子集数组的每个元素是否包含在HashSet. 这是一个非常快速的操作。

于 2013-03-26T03:08:47.753 回答
1

我有两种不同的解决方案

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

  • 第一个解决方案遍历两个数组并进行比较， 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和值 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);
}
于 2016-12-05T12:13:08.657 回答
1

外层循环一一挑选 arr2[] 的所有元素。内循环线性搜索外循环选取的元素。如果找到所有元素，则返回 true，否则返回 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;
}

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

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;

}

于 2016-07-22T07:06:37.733 回答
0

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

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

于 2018-12-27T21:52:51.943 回答
-1

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

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;
}
于 2013-03-26T03:13:41.837 回答