当前位置： 2024华为OD机试题库 (B卷,100分)- 事件推送（Java & JS & Python & C）

(B卷,100分)- 事件推送（Java & JS & Python & C）

2024-05-07 24

题目描述

同一个数轴X上有两个点的集合A={A1, A2, …, Am}和B={B1, B2, …, Bn}，Ai和Bj均为正整数，A、B已经按照从小到大排好序，

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

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

输入描述

第一行三个正整数m,n,R

第二行m个正整数,表示集合A

第三行n个正整数,表示集合B

输入限制：

1<=R<=100000, 1<=n,m<=100000, 1<=Ai,Bj<=1000000000

输出描述

每组数对输出一行Ai和Bj,以空格隔开

用例

输入 4 5 5
1 5 5 10
1 3 8 8 20
输出 1 1
5 8
5 8
说明 无

题目解析

本题数量级非常大，因此使用双重for是肯定会超时的。

我的解题思路是利用二分查找。

关于标准二分查找的实现可以参考Java的Arrays.binarySearch，其他语言实现可以看：

中关于binarySearch的具体实现，特别是其中关于有序插入位置的实现原理。

本题，我们只需要遍历每一个a[i]，然后通过二分查找去找他们在b中的位置 j ：

  • 如果 j >= 0，则说明b数组中有一个b[j] == a[i]，此时a[i] b[j]就是符合要求的组合
  • 如果 j < 0，则说明b数组中没有b[j] == a[i]，此时 j 其实就是 – insertIdx – 1，其中insertIdx就是a[i]在b中的有序插入位置，因此b[insertIdx] > a[i]，如果 b[insertIdx] – a[i] <= r，那么a[i] b[insertIdx]就是符合要求的组合

上面算法的事件复杂度只有O(nlogn)，不会超时。

2023.06.15

找到的有序插入位置可能 insertIdx == b.length，即使越界位置，此情况b数组中不存在比a[i]大的值

2023.07.08

本题最优策略为同向双指针，可达O(n)时间复杂度

二分查找解法

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    Integer[] tmp =
        Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

    int m = tmp[0];
    int n = tmp[1];
    int r = tmp[2];

    Integer[] a =
        Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

    Integer[] b =
        Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

    getResult(r, a, b);
  }

  public static void getResult(int r, Integer[] a, Integer[] b) {
    for (int ai : a) {
      int j = Arrays.binarySearch(b, ai);

      // 如果在b数组中可以找到ai，则此时j就是ai在b数组中的位置，此时ai和bj是满足要求，且最接近的
      if (j >= 0) {
        System.out.println(ai + " " + b[j]);
      } else {
        // 如果在b数组中找不到ai，则此时j就是ai在b数组中有序插入位置-insertIdx-1，
        // 因此insertIdx = -j-1，此时b[insertIdx]满足大于ai，我们只需要检查b[insertIdx] - ai<=r即可
        int insertIdx = -j - 1;
        // 有序插入位置可能是越界位置
        if (insertIdx == b.length) continue;
        if (b[insertIdx] - ai <= r) System.out.println(ai + " " + b[insertIdx]);
      }
    }
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const { userInfo } = require("os");
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 3) {
    let [m, n, r] = lines[0].split(" ").map((ele) => parseInt(ele));
    let a = lines[1].split(" ").map(Number);
    let b = lines[2].split(" ").map(Number);
    getResult(a, b, r);
    lines.length = 0;
  }
});

function getResult(a, b, r) {
  for (let ai of a) {
    const j = binarySearch(b, ai);
    if (j >= 0) {
      console.log(`${ai} ${b[j]}`);
    } else {
      const insertIdx = -j - 1;
      if (insertIdx == b.length) continue;
      if (b[insertIdx] - ai <= r) console.log(`${ai} ${b[insertIdx]}`);
    }
  }
}

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = (low + high) >> 1;
    const midVal = arr[mid];

    if (midVal > target) {
      high = mid - 1;
    } else if (midVal < target) {
      low = mid + 1;
    } else {
      return mid;
    }
  }

  return -low - 1;
}

Python算法源码

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


def binarySearch(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) >> 1
        midVal = arr[mid]

        if midVal > target:
            high = mid - 1
        elif midVal < target:
            low = mid + 1
        else:
            return mid

    return -low - 1


# 算法入口
def getResult():
    for ai in a:
        j = binarySearch(b, ai)
        if j >= 0:
            print(f"{ai} {b[j]}")
        else:
            insertIdx = -j - 1
            if insertIdx == len(b):
                continue
            if b[insertIdx] - ai <= r:
                print(f"{ai} {b[insertIdx]}")


# 算法调用
getResult()

C算法源码

#include <stdio.h>

int binarySearch(const int nums[], int nums_size, int key) {
    int low = 0;
    int high = nums_size - 1;

    while(low <= high) {
        int mid = (low + high) >> 1;
        int midVal = nums[mid];

        if(midVal > key) {
            high = mid - 1;
        } else if(midVal < key) {
            low = mid + 1;
        } else {
            return mid;
        }
    }

    return -low - 1;
}

int main() {
    int m, n, r;
    scanf("%d %d %d", &m, &n, &r);

    int a[m];
    for(int i=0; i<m; i++) {
        scanf("%d", &a[i]);
    }

    int b[n];
    for(int i=0; i<n; i++) {
        scanf("%d", &b[i]);
    }

    for(int i=0; i<m; i++) {
        int j = binarySearch(b, n, a[i]);

        if(j >= 0) {
            printf("%d %dn", a[i], b[j]);
        } else {
            int insertIdx = -j - 1;

            if(insertIdx == n) {
                continue;
            }

            if(b[insertIdx] - a[i] <= r) {
                printf("%d %dn", a[i], b[insertIdx]);
            }
        }
    }

    return 0;
}

同向双指针解法

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    Integer[] tmp =
        Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

    int m = tmp[0];
    int n = tmp[1];
    int r = tmp[2];

    int[] a = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    int[] b = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    getResult(r, a, b);
  }

  public static void getResult(int r, int[] a, int[] b) {
    int i = 0;
    int j = 0;

    while (i < a.length && j < b.length) {
      if (a[i] <= b[j]) {
        if (b[j] - a[i] <= r) System.out.println(a[i] + " " + b[j]);
        i++;
      } else {
        j++;
      }
    }
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const { userInfo } = require("os");
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 3) {
    let [m, n, r] = lines[0].split(" ").map((ele) => parseInt(ele));
    let a = lines[1].split(" ").map(Number);
    let b = lines[2].split(" ").map(Number);
    getResult(a, b, r);
    lines.length = 0;
  }
});

function getResult(a, b, r) {
  let i = 0;
  let j = 0;

  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) {
      if (b[j] - a[i] <= r) console.log(a[i] + " " + b[j]);
      i++;
    } else {
      j++;
    }
  }
}

Python算法源码

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


# 算法入口
def getResult():
    i = 0
    j = 0

    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            if b[j] - a[i] <= r:
                print(f"{a[i]} {b[j]}")
            i += 1
        else:
            j += 1


# 算法调用
getResult()

 

C算法源码

#include <stdio.h>

int main() {
    int m, n, r;
    scanf("%d %d %d", &m, &n, &r);

    int a[m];
    for(int i=0; i<m; i++) {
        scanf("%d", &a[i]);
    }

    int b[n];
    for(int i=0; i<n; i++) {
        scanf("%d", &b[i]);
    }

    int i = 0;
    int j = 0;

    while(i < m && j < n) {
        if(a[i] <= b[j]) {
            if(b[j] - a[i] <= r) {
                printf("%d %dn", a[i], b[j]);
            }
            i++;
        } else {
            j++;
        }
    }

    return 0;
}

 

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

0

评论0

取消

首页 发现 VIP 我的

站点公告

没有账号？注册  忘记密码？