刷题笔记合集🔗

事件推送

问题描述

小毛在一个数轴 X 上管理着两个点的集合 和 ，其中 和 均为正整数，A、B 已经按照从小到大排好序。

A、B 均不为空，给定一个距离 （正整数），请列出同时满足如下条件的所有 数对：

1. 
2. 之间的距离小于等于
3. 在满足 1,2 的情况下，每个 只需输出距离最近的
4. 输出结果按 从小到大的顺序排序

输入格式

第一行三个正整数 , , 。

第二行 个正整数，表示集合 。

第三行 个正整数，表示集合 。

输入限制：

, ,

输出格式

每组数对输出一行 和 ，以空格隔开。

样例输入

4 5 5
1 5 5 10
1 3 8 8 20

样例输出

1 1
5 8
5 8

数据范围

样例	解释说明
样例1	对于 ，满足条件的是 ；对于 ，满足条件的是 ；对于 ，没有满足条件的 。

题解

这道题目要求我们找出满足特定条件的所有数对 。关键条件是 且它们之间的距离不超过 ，并且每个 只对应距离最近的 。

思路分析

这道题有两种主要解法：二分查找和双指针。

二分查找解法

对于数组 A 中的每个元素 ，我们需要找到满足条件的 :

1. 先用二分查找找到与 相等的 ，如果找到，这就是最近的点
2. 如果找不到等值点，则根据二分查找返回的插入位置，检查右侧的元素是否满足

二分查找的时间复杂度是 O(log n)，对于每个 都需要进行一次查找，所以总体时间复杂度是 O(m log n)，这对于题目给出的数据范围 (m, n 最大为 100,000) 是可接受的。

双指针解法

双指针解法更为高效，时间复杂度可以优化到 O(m + n):

1. 初始化两个指针 i 和 j 分别指向数组 A 和 B 的起始位置
2. 如果 且 ，则记录这对数字，并移动指针 i
3. 否则，移动指针 j 来寻找可能满足条件的下一个

双指针解法利用了数组已经排序的特性，通过线性扫描找到所有符合条件的数对，避免了对每个 都进行二分查找的开销。

时间复杂度分析

• 二分查找解法：O(m log n)
• 双指针解法：O(m + n)

对于题目给出的数据范围 (m, n 最大为 100,000)，双指针解法明显更具优势，特别是在两个数组长度接近的情况下。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
m, n, r = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

def process_data():
    """使用双指针方法查找满足条件的数对"""
    i, j = 0, 0
    
    # 双指针遍历
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            # 如果满足距离条件，输出并移动a的指针
            if b[j] - a[i] <= r:
                print(f"{a[i]} {b[j]}")
            # 无论满不满足距离条件，都需要移动a指针
            i += 1
        else:
            # 如果a[i] > b[j]，移动b指针
            j += 1

# 调用函数
process_data()

• Cpp

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int>& a, vector<int>& b, int r) {
    // 使用双指针查找满足条件的数对
    int i = 0, j = 0;
    int m = a.size(), n = b.size();
    
    while (i < m && j < n) {
        // 如果a[i]小于等于b[j]，检查距离条件
        if (a[i] <= b[j]) {
            // 如果距离小于等于r，输出这对数字
            if (b[j] - a[i] <= r) {
                cout << a[i] << " " << b[j] << endl;
            }
            // 移动a的指针
            i++;
        } else {
            // 如果a[i]大于b[j]，移动b的指针
            j++;
        }
    }
}

// 二分查找方法的实现
void solve_binary(vector<int>& a, vector<int>& b, int r) {
    for (int ai : a) {
        // 二分查找ai在b中的位置
        auto it = lower_bound(b.begin(),