两数组配对最小绝对差算法的数学证明探究

Awesome question—intuition is great, but let's dig into the math to prove why sorting both arrays and checking corresponding positions gives you the minimal absolute difference between any pair of elements from A and B. Let's break this down clearly.

First, restate the problem #

We’ve got two arrays (A) and (B) (in your example, they’re the same length, which we’ll focus on here—we can tweak this for different lengths later). Our goal is to find any pair ((a, b)) where (a \in A), (b \in B), such that the absolute difference (|a - b|) is as small as possible.

Why sorting is the critical first step #

When we sort (A) into (A_{\text{sorted}} = [a_1, a_2, ..., a_n]) (so (a_1 \leq a_2 \leq ... \leq a_n)) and (B) into (B_{\text{sorted}} = [b_1, b_2, ..., b_n]) (same non-decreasing order), we leverage monotonicity—each element is at least as large as the one before it. This ordered structure lets us make logical, provable claims about how pairs of elements relate to each other.

The proof: why corresponding positions hold the minimal difference #

Let’s use a contradiction argument to show that the smallest possible (|a - b|) has to come from a pair ((a_i, b_i)) (same index in both sorted arrays), or at least there’s a corresponding pair with the same minimal value.

Suppose the opposite is true: the smallest absolute difference comes from a pair ((a_i, b_j)) where (j \neq i). Let’s assume (j > i) (the case where (j < i) works symmetrically, just reversed).

Since both arrays are sorted:

• (a_i \leq a_{i+1} \leq ... \leq a_j)
• (b_i \leq b_{i+1} \leq ... \leq b_j)

Now, let’s analyze the corresponding pair ((a_i, b_i)):

• If (a_i \leq b_i), then (|a_i - b_i| = b_i - a_i). Since (b_j \geq b_i), (b_j - a_i) (which equals (|a_i - b_j|)) is at least as large as (b_i - a_i). This means (|a_i - b_j|) can’t be smaller than (|a_i - b_i|)—directly contradicting our assumption that it’s the minimal difference. (The only exception is if (b_i = b_j), but then (|a_i - b_i| = |a_i - b_j|), so the corresponding pair still gives us the same minimal value.)
• If (a_i > b_i), then (|a_i - b_i| = a_i - b_i). Now, if (b_j \geq a_i), then (|a_i - b_j| = b_j - a_i). For this to be smaller than (|a_i - b_i|), we’d need (b_j - a_i < a_i - b_i), which simplifies to (b_i + b_j < 2a_i). But since (a_j \geq a_i) and (b_j \geq b_i), let’s look at the pair ((a_j, b_j)):
  • If (a_j \geq b_j), then (|a_j - b_j| = a_j - b_j). Since (a_j \geq a_i), this is at least (a_i - b_j = |a_i - b_j|). But if (|a_i - b_j|) is minimal, this means (a_i = a_j), so (|a_j - b_j| = |a_i - b_j|)—again, the corresponding pair gives the same minimal value.
  • If (a_j < b_j), then (|a_j - b_j| = b_j - a_j). Since (a_j \geq a_i), this is smaller than or equal to (b_j - a_i = |a_i - b_j|), which contradicts our assumption that (|a_i - b_j|) is the smallest difference—unless (a_i = a_j), making the differences equal.

In every scenario, either the corresponding position pair has a smaller difference, or it’s equal to the supposed minimal non-corresponding pair. That means our initial assumption was wrong: the minimal absolute difference must exist in the set of corresponding pairs from the sorted arrays.

A quick note for different-length arrays #

If (A) and (B) have different lengths, you can use a two-pointer approach instead: start at the beginning of both sorted arrays, move the pointer pointing to the smaller element forward, and track the minimal difference as you go. But your original method works perfectly when the arrays are the same length!

内容的提问来源于stack exchange，提问作者John Lexus