查找出現在第一個數組中而不是第二個數組中的元素


難度級別 容易獎學金
經常問 ol石 德里韋里 事實集 狂徒 Snapdeal 百會
排列 哈希

問題“查找出現在第一個數組中而不是第二個數組中的元素”指出您得到了兩個 數組。 數組由所有 整數。 您必須找出將不會出現在第二個數組中但出現在第一個數組中的數字。

查找出現在第一個數組中而不是第二個數組中的元素

a [] = {2,4,3,1,5,6}
b [] = {2,1,5,6}
4 3
a [] ={4,2,6,8,9,5}
b [] ={9,3,2,6,8}
4

算法

  1. 聲明一個 哈希集.
  2. 將數組b []的所有元素插入HashSet。
  3. 當i <l1(數組a []的長度)時。
    1. 如果HashSet不包含數組a [i],則打印a [i]。

解釋

我們給出了兩個整數數組和一個問題語句,該語句要求找出第一個數組而不是第二個數組中存在的數字。 我們將要使用 哈希 在這個問題上。 哈希可以幫助我們有效地找到解決方案。

我們將把數組b []的數字放入HashSet中,然後插入數組b []的所有數字。 我們將遍歷數組a []並一次獲取每個元素,並檢查HashSet是否不包含該元素。 如果它沒有那個元素,我們將打印數組a [i]的那個特定元素並檢查另一個數字。

讓我們考慮一個示例並理解這一點:

第一個數組是a [] = a [] = {2,6,8,9,5,4},b [] = {9,5,2,6,8}

我們必須將數組b []的所有元素插入HashSet中,因此在HashSet中,我們具有以下值:

HashSet:{9,5,2,6,8} //基本上b []的所有值。

我們將遍歷數組a []並獲取其每個元素並檢查條件。

i = 0,a [i] = 2

2位於HashSet中,因此將不會打印。

i = 1,a [i] = 6

6在HashSet中,再次將不會打印。

i = 2,a [i] = 8

HashSet中有8,它將不會被打印。

i = 3,a [i] = 9

9位於HashSet中,因此將不會打印。

i = 4,a [i] = 5

5在HashSet中,再次將不會打印。

i = 5,a [i] = 4

4不在HashSet中,因此這一次它將被打印,表示它是存在於數組a []中但不是出現在數組b []中的數字,因為基本上HashSet是數組b []的克隆,我們的輸出將變成“ 4”。

C ++代碼查找存在於第一個數組而不是第二個數組中的元素

#include<unordered_set>
#include<iostream>
using namespace std;

void getMissingElement(int A[], int B[], int l1, int l2)
{
  unordered_set <int> myset;

  for (int i = 0; i < l2; i++)
    myset.insert(B[i]);

  for (int j = 0; j < l1; j++)
    if (myset.find(A[j]) == myset.end())
      cout << A[j] << " ";
}
int main()
{
    int a[] = { 9, 2, 3, 1, 4, 5 };
    int b[] = { 2, 4, 1, 9 };
  int l1 = sizeof(a) / sizeof(a[0]);
  int l2 = sizeof(b) / sizeof(b[0]);
  getMissingElement(a, b, l1, l2);
  return 0;
}
3 5

Java代碼查找存在於第一個數組而不是第二個數組中的元素

import java.util.HashSet;
import java.util.Set;

class missingElement
{
    public static void getMissingElement(int A[], int B[])
    {
        int l1 = A.length;
        int l2 = B.length;

        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < l2; i++)
            set.add(B[i]);

        for (int i = 0; i < l1; i++)
            if (!set.contains(A[i]))
                System.out.print(A[i]+" ");
    }
    public static void main(String []args)
    {
        int a[] = { 9, 2, 3, 1, 4, 5 };
        int b[] = { 2, 4, 1, 9 };

        getMissingElement(a, b);
    }
}
3 5

複雜度分析

時間複雜度

上) 哪裡 “ N” 是array1中元素的數量。 因為使用HashSet進行插入和搜索使我們能夠在O(1)中執行這些操作。 因此,時間複雜度是線性的。

空間複雜度

上) 哪裡 “ N” 是array1中元素的數量。 由於我們正在存儲第二個數組的元素。 因此,所需空間與第二個數組的大小相同。