1 条题解

  • 0
    @ 2026-1-28 15:19:04
    #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
    上传者