整数散列

问题描述

两次输入n，和m个整数，计算后面输入的数 有多少前面出现过

算法思路

通过以空间换时间的方法，增添一个数组，x是第一次输入的数，A【x】来记录又没出现过

算法分析

1.时间复杂度：T（n） = O（n）
2.空间复杂度：S（n） = O（n）

算法实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
int main() {
 int A[100],cout=0;
 int n, m, i,x;
 std::cin >> n >> m;
 memset(A, 0, sizeof(A));
 for ( i = 0; i < n; i++)
 {
  std::cin >> x;
  A[x] = !A[x];
 }
 for ( i = 0; i < m; i++)
 {
  std::cin >> x;
  if (A[x])
   cout++;
 }
 printf("%d", cout);
 system("pause");
 return 0;
}