查找出现在第一个数组而不是第二个数组中的元素  


难度级别 易得奖学金
经常问 ol石 德里韦里 事实集 狂徒 Snapdeal 百会
排列 哈希

问题“查找第一个数组中没有的元素,而不是第二个数组中的元素”指出您得到了两个 数组。 数组由所有 整数。 您必须找出将不会出现在第二个数组中但出现在第一个数组中的数字。

使用案列  

查找出现在第一个数组而不是第二个数组中的元素Pin

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)中执行这些操作。 因此,时间复杂度是线性的。

参见
按最小字符Leetcode解决方案的频率比较字符串

空间复杂度

上) 哪里 “N” 是array1中元素的数量。 由于我们正在存储第二个数组的元素。 因此,所需空间与第二个数组的大小相同。