当前位置: 面试刷题>> 两个数组最小差问题 (经典算法题500道)


完整题目描述

题目名称:两个数组的最小差问题

给定两个非空整数数组 nums1nums2,要求从 nums1 中选择一个元素,从 nums2 中选择另一个元素,计算这两个元素之差的绝对值,并找出所有可能组合中的最小差值。

示例 1

输入: nums1 = [1, 3, 15], nums2 = [2, 5, 7]
输出: 1
解释: 选择 nums1 中的 1 和 nums2 中的 2,|1 - 2| = 1 是最小的差值。

示例 2

输入: nums1 = [1, 5, 12], nums2 = [2, 7, 11]
输出: 3
解释: 选择 nums1 中的 5 和 nums2 中的 2,|5 - 2| = 3 是最小的差值。

注意

  1. 1 <= nums1.length, nums2.length <= 10^5
  2. -10^9 <= nums1[i], nums2[i] <= 10^9

解题思路

为了高效地解决这个问题,我们可以首先对两个数组进行排序,然后使用双指针技术来遍历这两个数组。通过移动指针,我们可以逐步接近两个数组中可能的最小差值。

PHP 代码示例

function minAbsoluteDifference(array $nums1, array $nums2) {
    sort($nums1);
    sort($nums2);
    
    $minDiff = PHP_INT_MAX;
    $i = $j = 0;
    
    while ($i < count($nums1) && $j < count($nums2)) {
        $diff = abs($nums1[$i] - $nums2[$j]);
        $minDiff = min($minDiff, $diff);
        
        if ($nums1[$i] < $nums2[$j]) {
            $i++;
        } else {
            $j++;
        }
    }
    
    return $minDiff;
}

// 示例用法
$nums1 = [1, 3, 15];
$nums2 = [2, 5, 7];
echo minAbsoluteDifference($nums1, $nums2);  // 输出 1

Python 代码示例

def minAbsoluteDifference(nums1, nums2):
    nums1.sort()
    nums2.sort()
    
    min_diff = float('inf')
    i, j = 0, 0
    
    while i < len(nums1) and j < len(nums2):
        diff = abs(nums1[i] - nums2[j])
        min_diff = min(min_diff, diff)
        
        if nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    
    return min_diff

# 示例用法
nums1 = [1, 3, 15]
nums2 = [2, 5, 7]
print(minAbsoluteDifference(nums1, nums2))  # 输出 1

JavaScript 代码示例

function minAbsoluteDifference(nums1, nums2) {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);
    
    let minDiff = Infinity;
    let i = j = 0;
    
    while (i < nums1.length && j < nums2.length) {
        const diff = Math.abs(nums1[i] - nums2[j]);
        minDiff = Math.min(minDiff, diff);
        
        if (nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }
    
    return minDiff;
}

// 示例用法
const nums1 = [1, 3, 15];
const nums2 = [2, 5, 7];
console.log(minAbsoluteDifference(nums1, nums2));  // 输出 1

码小课网站中有更多关于算法和数据结构的内容,包括各种经典问题的解析和代码实现,欢迎大家学习交流。

推荐面试题