C語言實作：計算兩陣列元素差值的最小絕對值（最短距離）

兩陣列最短距離計算

給定兩個陣列 num[] 與 cou[]，找出所有配對 (x, y) 中絕對差值 |x - y| 的最小值。此為「最短距離」問題。

問題描述

num[] = {1, 3, 5, 7, 9} (5元素)，cou[] = {2, 4, 6, 8} (4元素)。
共 20 種配對，計算各配對絕對差值並找出最小值。

基本解法：暴力枚舉 O(m×n)

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i, j, k = 0, min;
    int diff[20];
    int num[] = {1, 3, 5, 7, 9};
    int cou[] = {2, 4, 6, 8};

    for(i = 0; i < 4; i++)
        for(j = 0; j < 5; j++)
            diff[k++] = abs(cou[i] - num[j]);

    min = diff[0];
    for(i = 0; i < k; i++)
        if(diff[i] < min) min = diff[i];

    printf("陣列num[]與陣列cou[]差的絕對值最小為%d\n", min);
    return 0;
}

手動驗證

相鄰數字差值：|1-2|=1, |2-3|=1, |3-4|=1, |4-5|=1, |5-6|=1, |6-7|=1, |7-8|=1, |8-9|=1。
最小值 = 1。

最佳化：排序後雙指針 O(m log m + n log n)

將兩陣列排序，雙指針同步遍歷：

sort(num, 5); sort(cou, 4);
int i = 0, j = 0, min = INT_MAX;
while(i < 5 && j < 4) {
    min = fmin(min, abs(num[i] - cou[j]));
    if(num[i] < cou[j]) i++;
    else j++;
}

只需比較「當前最近」的配對，大幅減少比較次數。

空間優化

基本解法用 diff[20] 儲存所有差值，實際上只需一個變數即時更新最小值，無需額外陣列：

int min = INT_MAX;
for(i = 0; i < 4; i++)
    for(j = 0; j < 5; j++)
        min = fmin(min, abs(cou[i] - num[j]));

應用場景

• 最近鄰搜尋、向量量化、時間序列相似度比對。
• 地理資訊系統：兩組座標點的最近距離。