查找一個數組是否是另一個數組的子集  


難度級別 容易獎學金
經常問 ol石 GE醫療集團 高通公司
排列 二元搜尋 哈希 搜索 排序

問題“查找一個數組是否是另一個數組的子集”指出給您兩個數組arra1 []和array2 []。 給定的數組是未排序的。 您的任務是查找array2 []是否是array1 []的子集。

例  

查找一個數組是否是另一個數組的子集

arr1= [1,4,5,7,8,2]
arr2= [1,7,2,4]
arr2 [] is a subset of arr1 [].
arr1= [21,4,5,2,18,3]
arr2= [1,4,2,3]
arr2 [] is not a subset of arr1 [].

算法  

  1. 打開一個嵌套循環。
  2. 將i設為0,j設為0。
  3. i 小於array2 []的長度。
    1. j 小於array1 []的長度。
      1. 如果arr2 [i]等於arr [j],則中斷。
  4. If j 等於m,返回false。
  5. 返回true。

解釋

我們的任務是查找是否 排列 第二個是array1的子集。 因此,我們的主要思想是使用嵌套循環並檢查每個元素,並在array2中找到array1的每個元素,這意味著array2是array1的子集。

讓我們以一個示例作為我們在array1和array2中的輸入

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

從array0的第2個索引開始,我們將檢查arrays0的第2個索引在array1 [i]中是否找到相似的數字,是的,它發現它的值為11。因此,我們將打破循環並執行i ++。

也可以看看
最長的雙子序列

從array1 []的第一個索引開始,我們將檢查arrays2的第一個索引在array1 [i]中是否找到相似的數字,是的,它找到的是2。因此,我們將打破循環並執行i ++ 。

從array2 []的第二個索引開始,我們將檢查arrays2的第二個索引在array2 [i]中是否找到相似的數字,並且發現它的值為2。因此,我們將打破循環並執行i ++。

從array1 []的第一個索引開始,我們將檢查arrays2的第一個索引在array1 [i]中是否找到相似的數字,是否有2找到它。 因此,我們將打破循環並開始使用i ++。

關於if條件表示為if(j = = m),這意味著,如果在任何迭代中,如果在array2 []中未找到array1的任何元素,則表示它脫離了循環而沒有中斷,這意味著'j '的值等於array1 []的長度,這意味著我們沒有找到與array1 []類似的元素之一,並且由於子集包含給定集合的所有元素,所以我們返回false一。

推薦碼  

C ++代碼查找一個數組是否為另一個數組的子集

#include <iostream>
using namespace std;

bool isSubset(int arr1[], int arr2[], int l1, int l2)
{
    int i,j;
    for(i=0; i<l2; i++)
    {

        for(j=0; j<l1; j++)
        {
            if(arr2[i]==arr1[j])
                break;
        }
        if(j==l1)
            return false;
    }
    return true;
}
int main()
{
    int arr1[] = {1, 2, 3, 4, 5, 6};
    int arr2[] = {1, 3, 5};

    int l1=sizeof(arr1)/sizeof(arr1[0]);
    int l2=sizeof(arr2)/sizeof(arr2[0]);
    if(isSubset(arr1,arr2,l1,l2))
    {
        cout<<"arr2[] is a subset of arr1[]";
    }
    else
    {
        cout <<"arr2[] is not a subset of arr1[]"<<endl;
    }
    return 0;
}
arr2[] is a subset of arr1[]

Java代碼查找一個數組是否是另一個數組的子集

class isArraySubset
{
    public static boolean isSubset(int arr1[],int arr2[], int l1, int l2)
    {
        int i = 0;
        int j = 0;
        for (i = 0; i < l2; i++)
        {
            for (j = 0; j < l1; j++)
            {
                if(arr2[i] == arr1[j])
                {
                    break;
                }
            }
            if (j == l1)
                return false;
        }
        return true;
    }
    public static void main(String args[])
    {
        int arr1[] = {1, 2, 3, 4, 5, 6};
        int arr2[] = {1, 3, 5};

        int l1 = arr1.length;
        int l2 = arr2.length;

        if(isSubset(arr1, arr2, l1, l2))
        {
            System.out.println("arr2[] is a subset of arr1[]");
        }
        else
        {
            System.out.println("arr2[] is not a subset of arr1[]");
        }
    }
}
arr2[] is a subset of arr1[]

複雜度分析  

時間複雜度

O(米* n) 哪裡 “m”個 是arr1的大小,並且 “ n” 是arr2的大小。 因為我們使用了嵌套循環,所以使時間複雜度成為多項式。

也可以看看
最大總和增加子序列

空間複雜度

O(1), 因為我們沒有使用任何額外的數組/向量。