面试题 16.06.最小差

1. 题目描述

给定两个整数数组 a 和 b ，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差

示例：

输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出：3，即数值对(11, 8)

提示：

• 1 <= a.length, b.length <= 100000
• -2147483648 <= a[i], b[i] <= 2147483647
• 正确结果在区间 [0, 2147483647] 内

标签 数组 双指针 二分查找 排序

2. 解题

1. 暴力解法，时间复杂度O(n^2)

2. 排序+双指针

• 先将两个数组进行排序
• 初始化两个指针i, j分别指向两个数组的开始
• 记min := abs(arr1[i]-arr2[j]), 循环执行如下操作, 直到i >= len(arr1)-1 || j >= len(arr2)-1
  • 如果abs(arr1[i+1]-arr2[j]) > abs(arr1[i]-arr2[j+1]), 那么j++
  • 如果abs(arr1[i+1]-arr2[j]) < abs(arr1[i]-arr2[j+1]), 那么i++
  • 如果abs(arr1[i+1]-arr2[j]) == abs(arr1[i]-arr2[j+1]), i++, j++