快速判断某一个数组是否是另一个数组的子集

87 阅读 0 评论 58 点赞

我是靠谱客的博主鲜艳大神，最近开发中收集的这篇文章主要介绍快速判断某一个数组是否是另一个数组的子集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给定两个无序数组：数组arr1[0…m-1] 和数组arr2[0…n-1] ,判断数组arr2是否是arr1的子集。

比如

arr1[] = {11, 1, 13, 21, 3, 7}
arr2[] = {11, 3, 7, 1}

输出true

arr1[] = {1, 2, 3, 4, 5, 6},
arr2[] = {1, 2, 4}

输出true

arr1[] = {10, 5, 2, 23, 19}
arr2[] = {19, 5, 3}

输出false

方法1

使用两个for循环。外部循环挑选出arr2[]的每一个元素赋值为value；然后再内部循环中，搜索在arr1[]中是否存在value。如果arr2[]中的每一个元素都可以在arr1[]中被找到，则返回true，否则返回false。具体代码如下：

boolean isSubset(int arr1[],  
                int arr2[], int m, int n) 
    { 
        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 the above inner loop  
            was not broken at all then 
            arr2[i] is not present in 
            arr1[] */
            if (j == m) 
                return false; 
        } 
          
        /* If we reach here then all 
        elements of arr2[] are present 
        in arr1[] */
        return true; 
}

方法2

1 先将两个数组分别进行排序
2 然后用Merge Type(合并类型)的过程, 判断arr2[]是否是arr1[]的子集

boolean isSubset(int arr1[], int arr2[], int m, int n) 
    { 
        int i = 0, j = 0; 
              
        if(m < n) 
        return false; 
          
        Arrays.sort(arr1); //sorts arr1 
        Arrays.sort(arr2); // sorts arr2 
  
        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; 
}

因为要对两个数组分别进行排序，所以时间复杂度为O(mLogm + nLogn)

方法3(使用HashSet)

1 创建一个HashSet，并将数组arr1[]中的所有元素保存到此HashSet中
2 遍历arr2[], 并在HashSet中搜索arr2[]的每一个元素. 如果某一个元素没有找到则返回0.
3 如果arr2[]中的每一个元素都可以在HashSet中找到，则返回1

boolean isSubset(int arr1[], int arr2[], int m, int n) 
    { 
        HashSet<Integer> hset= new HashSet<>(); 
          
        // hset stores all the values of arr1 
        for(int i = 0; i < m; i++) 
        { 
            if(!hset.contains(arr1[i])) 
                hset.add(arr1[i]); 
        } 
              
        // loop to check if all elements of arr2 also 
        // lies in arr1 
        for(int i = 0; i < n; i++) 
        { 
            if(!hset.contains(arr2[i])) 
                return false; 
        } 
        return true; 
}