1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // 全局数组:arr存储第一组数字,brr存储第二组数字 int arr[101000], brr[101000]; // [1] 二分查找函数:在已排序的arr数组中查找数字a,找到返回索引,否则返回-1 int f(int a, int n){ int left = 0, right = n - 1; while(left <= right){ int mid = (left + right) / 2; if(arr[mid] < a) // 目标值在右半区间 left = mid + 1; else if(arr[mid] > a) // 目标值在左半区间 right = mid - 1; else // 找到目标值,返回索引 return mid; } return -1; // 未找到目标值 } int main(){ int n, m; // [2] n:第一组数字的数量;m:第二组数字的数量 cin >> n >> m; // [3] 输入第一组数字,存入arr数组 for(int i = 0; i < n; i++) cin >> arr[i]; // [4] 输入第二组数字,存入brr数组 for(int i = 0; i < m; i++) cin >> brr[i]; // [5] 对两组数字分别进行升序排序 sort(arr, arr + n); sort(brr, brr + m); // [6] 遍历第二组数字,用二分查找判断是否在第一组中存在,存在则输出 for(int i = 0; i < m; i++){ if(f(brr[i], n) >= 0) // 查找结果>=0表示存在 cout << brr[i] << " "; } return 0; }
- 1
信息
- ID
- 1218
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者