问题

问题描述

小R在研究两个数列之间的关系。他给定了两个数列 a 和 b，长度分别为 n 和 m，并设计了一个有趣的公式：$$∣(a[i]−b[j])^2−k^2∣∣(a[i]−b[j])^2−k^2∣$$，其中 k 是给定的一个整数， $$0≤i。现在，小R想知道如何选择数列 a 和 b 中的元素 a[i]a[i] 和 b[j]b[j]，使得这个公式的值达到最小。

给定两个整数数列 a（长度为 n） 和 b（长度为 m），以及一个整数 k，你需要找到这个公式的最小值。

约束条件

• $$1≤n,m≤10^5$$
• $$0≤k≤10^9$$
• $$0≤a[i],b[j]≤10^9$$

测试样例

样例1：

输入：n = 5 ,m = 5, k = 1, a = [5, 3, 4, 1, 2] ,b = [0, 6, 7, 9, 8] 输出：0

解释：当选择 a[3] = 1 和 b[0] = 0 时，$$∣(1−0)^2−1^2∣=∣1−1∣=0$$，这是最小可能值。

样例2：

输入：n = 5 ,m = 5, k = 0 ,a = [5, 3, 4, 1, 2] ,b = [0, 6, 7, 9, 8] 输出：1

样例3：

输入：n = 5 ,m = 6, k = 3 ,a = [5, 3, 4, 1, 2] ,b = [0, 6, 7, 9, 8, 11] 输出：0

分析

好的，让我们来分析一下这个问题。

问题理解

你需要找到两个数列 a 和 b 中的元素 a[i] 和 b[j]，使得公式 $$∣(a[i]−b[j])^2−k^2∣ $$的值最小。

数据结构选择

由于数列 a 和 b 的长度可能非常大（最多 $$10^5$$），我们需要选择一种高效的算法来解决这个问题。

算法步骤

1. 排序：首先对数列 a 和 b 进行排序。排序后的数列可以帮助我们更快地找到最接近的元素。
2. 双指针法：使用**双指针法**来遍历排序后的数列 a 和 b。一个指针用于遍历 a，另一个指针用于遍历 b。
3. 计算公式值：在遍历过程中，计算公式 $$∣(a[i]−b[j])^2−k^2∣$$ 的值，并记录最小值。
4. 移动指针：根据当前计算的值，决定移动哪个指针。如果当前值较大，可以尝试移动指针以找到更接近的值。

具体步骤

1. 初始化：初始化两个指针 i 和 j，分别指向数列 a 和 b 的起始位置。
2. 遍历：在 i 和 j 的范围内，计算公式 $$∣(a[i]−b[j])^2−k^2∣$$ 的值。
3. 更新最小值：如果当前计算的值小于之前记录的最小值，则更新最小值。
4. 移动指针：根据当前计算的值，决定移动 i 还是 j。如果 a[i] 和 b[j] 的差值较大，可以尝试移动指针以找到更接近的值。
5. 返回结果：遍历结束后，返回记录的最小值。

通过这种方法，你可以在 $$O(n \log n + m \log m)$$ 的时间复杂度内解决问题，其中 n 和 m 分别是数列 a 和 b 的长度。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

fn solution(n: i32, m: i32, k: i32, a: Vec<i32>, b: Vec<i32>) -> i32 {
  // Please write your code here

  // 对数组 a 和 b 进行排序
  let mut a = a;
  let mut b = b;
  // 从小到大生序排列
  a.sort();
  b.sort();

  // 记录最小差值
  let mut min_diff = std::i32::MAX;
  // 创建两个指针，都指向数组起始位置，属于同向双指针
  let mut i = 0;
  let mut j = 0;

  // 使用双指针法遍历数组 a 和 b
  while i < n as usize && j < m as usize {
      // 计算当前的差值
      let diff = (a[i] - b[j]).abs();
      // 在遍历过程中，计算公式 ∣(a[i]−b[j])2−k2∣ 的值
      let current_value = (diff * diff - k * k).abs();

      // 更新最小差值，因为默认是i32的最大值，所以第一次一定会进入
      if current_value < min_diff {
          min_diff = current_value;
      }

      // 根据当前差值调整指针，如果 a[i] 和 b[j] 的差值较大，可以尝试移动指针以找到更接近的值。
      // 如果 a 比 b 的值小，则 a 的指针进一位
      if a[i] < b[j] {
          i += 1;
      // 如果 a 值大于等于 b 的值，则 b 的指针进一位
      } else {
          j += 1;
      }
  }

  min_diff
}

fn main() {
  // You can add more test cases here
  println!("{}", solution(5, 5, 1, vec![5, 3, 4, 1, 2], vec![0, 6, 7, 9, 8]) == 0);
  println!("{}", solution(5, 5, 0, vec![5, 3, 4, 1, 2], vec![0, 6, 7, 9, 8]) == 1);
  println!("{}", solution(5, 6, 3, vec![5, 3, 4, 1, 2], vec![0, 6, 7, 9, 8, 11]) == 0);
}