数组最小绝对差值计算代码输出异常，请求排查错误

问题描述 #

编写的C++代码用于计算数组中任意两个不同元素的最小绝对差值，但输入测试用例-5 -3 -1 0 2时，预期输出为1（-1与0的绝对差值），实际输出为2。

错误分析 #

1. heapify函数逻辑完全错误 #

原heapify函数试图构建堆，但比较条件是子节点与父节点的绝对差值和当前最小节点与父节点的绝对差值，这完全偏离了堆的构建逻辑。堆的构建应该基于元素本身的大小，而非元素与父节点的差值，这导致堆结构完全不符合预期，后续的差值计算也失去了正确性。

2. minAbsoluteDifference函数的比较逻辑不完整 #

原函数仅计算了每个元素与数组第一个元素的差值，没有遍历所有两两元素的组合，必然会遗漏真正的最小差值（比如测试用例中的-1和0）。同时，使用堆结构来解决这个问题属于思路错误，完全没必要。

解决方法 #

计算数组最小绝对差值的最优思路是：先对数组排序，然后遍历相邻元素的差值——因为排序后，最小的绝对差值一定出现在相邻元素之间。

修复后的完整代码 #

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int minAbsoluteDifference(int arr[], int n) {
    if (n < 2) return 0; // 处理数组元素不足2个的情况
    
    sort(arr, arr + n);
    int minDiff = INT_MAX;
    
    for (int i = 1; i < n; i++) {
        int diff = abs(arr[i] - arr[i-1]);
        if (diff < minDiff) {
            minDiff = diff;
        }
    }
    
    return minDiff;
}

int main() {
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;
    int arr[n];
    cout << "Enter the elements of the array:\n";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int minDiff = minAbsoluteDifference(arr, n);
    cout << "Minimum absolute difference between any two distinct elements in the array is: " << minDiff << endl;
    return 0;
}

代码说明 #

• 使用sort函数对数组排序，时间复杂度为O(n log n)，是该问题的最优时间复杂度之一。
• 遍历排序后的数组，仅比较相邻元素的绝对差值，记录最小值，遍历时间复杂度为O(n)。
• 增加了数组元素不足2个的边界处理，避免非法访问。

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