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

pprl5pva  于 2023-05-12  发布在  Java
关注(0)|答案(8)|浏览(129)

如何有效地检查一个整数数组中的所有元素是否是另一个数组中所有元素的子集?例如,[33 11 23]是[11 23 33 42]的子集。先谢谢你了。

roejwanj

roejwanj1#

如果你不需要使用Arrays,任何Java集合都有containsAll方法:

boolean isSubset = bigList.containsAll(smallList);

这将做你想要的,高效。

xzv2uavs

xzv2uavs2#

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

jobtbby3

jobtbby33#

假设你想检查A是B的子集。将B的每个元素放入一个散列中,然后迭代A中的元素,所有元素都必须存在于散列中

b5lpy0ml

b5lpy0ml4#

外部循环一个接一个地拾取arr2[]的所有元素。内部循环线性搜索外部循环拾取的元素。如果找到所有元素,则返回true,否则返回false

public boolean canCatch(int [] nums,int [] nums){

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

为什么要在排序后进行二分查找?由于这两个数组都可以以排序的形式使用,我们可以只使用两个指针,如下所示:
public boolean canCatch(int [] nums,int [] nums){

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;

}

3ks5zfa0

3ks5zfa05#

我带来了两种不同的解决方案
输入: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");
}
  • 第二解决方案使用具有来自1....9的键和作为0的值的散列图,

接下来,我们迭代主数组和+1以获得相应的值
接下来,我们迭代子数组和-1以获得相应的值
下一个比较两个数组长度之差的哈希Map值的和

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

azpvetkf6#

对两个数组进行排序,并检查较小数组中的所有元素是否存在于较大数组中。这不需要使用额外的空间。
如果没有,就像有人建议的那样使用hasmap。

pkln4tw6

pkln4tw67#

只需简单地将这两个数组转换为两个字符串,并比较一个字符串是否包含另一个字符串。

public static void main(String... args) {
    int[] nums1 = {1,0,0,0,1};
    int[] nums2 = {0,0,0};

    String mainString = "";
    for(int num : nums1) mainString += num;

    String subString = "";
    for(int i=0; i<nums2.length; i++) subString += "0";

    if(mainString.contains(subString)){
        System.out.println(true);
    } else {
        System.out.println(false);
    }
}
qacovj5a

qacovj5a8#

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

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

相关问题