【题目描述】

小A所在的学校又迎来了一年一度的开花活动，有 n 名学生被评为文学优秀奖，m 名学生被评为体育优秀奖。现已知两个奖项获奖同学的编号，每个同学都有唯一的编号。只有同时被评为文学优秀奖和体育优秀奖的学生才能开花，小A想知道开花的名单，请你帮他统计一下。

【输入描述】

第一行两个整数  ，分别表示文学优秀奖和体育优秀奖的获奖人数。

第二行 n 个不同的整数，表示获得文学优秀奖的同学编号。

第二行 m 个不同的整数，表示获得体育优秀奖的同学编号。

所有编号为正整数且不超过  。

【输出描述】

一行若干个空格分隔的整数，表示开花的同学编号，按文学优秀奖的先后次序输出。

【样例输入】

4 4  5 1 7 3  2 3 4 1

【样例输出】

 1 3

【题目分析】

根据样例，我们知道获得文学优秀奖的同学有 5 1 7 3，获得体育优秀奖的同学有 2 3 4 1。那么同时获得文学优秀奖和体育优秀奖的同学是 1 和 3，题目要求按照文学优秀奖获奖顺序输出。故而输出的结果是 3 1。

由于数据最大可能是 10^5，故算法必须优于 O(nlogn)。同时我们需要在体育优秀奖里搜索获得文学优秀奖名单。所以可以考虑用二分查找，这样算法的复杂度为 O(logn)。

1、读入文学优秀奖同学，存入数组 a。

2、读入体育优秀奖同学，存入数组 b。

3、排序数组 b，因为要在体育优秀奖里搜索文学优秀奖名单。

4、遍历数组 a，查看 a[i] 是否在数组 b 中。

【参考代码1】

#include <bits/stdc++.h>  using namespace std;     const int MAXN = 1e5+6;  const int MAXM = 1e5+6;  int a[MAXN];//文学优秀奖  int b[MAXM];//体育优秀奖     int main() {      //读入数据      int n,m,i;   	cin>>n>>m;       //读入文学优秀奖      for (i=0; i<n; i++) {          cin>>a[i];      }      //读入体育优秀奖      for (i=0; i<m; i++) {            cin>>b[i];      }      //排序      sort(b, b+m);      for (i=0; i<n; i++) {          if (binary_search(b, b+m, a[i])) {              cout<<a[i]<<" ";          }      }      printf("\n");         return 0;  }

【参考代码2】

#include<bits/stdc++.h>  using namespace std;  int t[100005];  int w[100005];  int binary_search(int x, int l, int r){      while(l <= r){          int mid = (l + r) >> 1;          if(t[mid] == x){              return mid;          }          if(t[mid] < x){              l = mid + 1;          }else{              r = mid - 1;          }      }      return -1;  }  int main(){      int n, m;      cin >> n >> m;      for(int i = 0; i < n; ++i){          cin >> w[i];      }      for(int i = 0; i < m; ++i){          cin >> t[i];      }      sort(t, t + m);      int t = 0;      for(int i = 0; i < n; ++i){          if(binary_search(w[i], 0, m - 1) != -1){              t++;              if(t == 1) cout << w[i];              else{                  cout << " " << w[i];              }                        }      }      return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});