如何用C++实现O(nlogn)复杂度的无序数组最小差值查找

实现思路 #

• 核心依据：无序数组的最小差值必然出现在其排序后的相邻元素中，我们可以改造归并排序流程，在排序过程中同步计算相邻元素差值，不需要排序完成后二次遍历，时间复杂度稳定为O(nlogn)。
• 流程拆分：
  1. 递归拆分待处理数组到长度为1的子数组
  2. 归并两个有序子数组时，同步计算归并过程中相邻元素的差值，全程记录最小差值
  3. 最终返回全局最小差值即可

针对你的示例输入[10, 30, 89, 120, 88, 3000, 5]，排序后相邻元素最小差值为89和88的差1，和示例输出一致。

完整实现代码 #

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int merge(vector<int>& arr, int left, int mid, int right, int current_min) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> left_arr(n1), right_arr(n2);
    
    for (int i = 0; i < n1; i++) left_arr[i] = arr[left + i];
    for (int j = 0; j < n2; j++) right_arr[j] = arr[mid + 1 + j];
    
    // 优先计算两个有序子数组交界的差值，大概率是当前区间的最小差值
    current_min = min(current_min, abs(left_arr.back() - right_arr[0]));
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (left_arr[i] <= right_arr[j]) {
            arr[k] = left_arr[i];
            if (k > left) current_min = min(current_min, abs(arr[k] - arr[k-1]));
            i++;
        } else {
            arr[k] = right_arr[j];
            if (k > left) current_min = min(current_min, abs(arr[k] - arr[k-1]));
            j++;
        }
        k++;
    }
    
    // 处理左子数组剩余元素
    while (i < n1) {
        arr[k] = left_arr[i];
        current_min = min(current_min, abs(arr[k] - arr[k-1]));
        i++;
        k++;
    }
    // 处理右子数组剩余元素
    while (j < n2) {
        arr[k] = right_arr[j];
        current_min = min(current_min, abs(arr[k] - arr[k-1]));
        j++;
        k++;
    }
    return current_min;
}

int mergeSortFindMinDiff(vector<int>& arr, int left, int right) {
    if (left >= right) return INT_MAX;
    int mid = left + (right - left) / 2;
    int left_min = mergeSortFindMinDiff(arr, left, mid);
    int right_min = mergeSortFindMinDiff(arr, mid + 1, right);
    int cur_min = min(left_min, right_min);
    return merge(arr, left, mid, right, cur_min);
}

int findMinDiff(vector<int>& arr) {
    if (arr.size() < 2) return 0; // 元素不足2个可根据需求调整返回逻辑
    return mergeSortFindMinDiff(arr, 0, arr.size() - 1);
}

// 测试示例
int main() {
    vector<int> test = {10, 30, 89, 120, 88, 3000, 5};
    cout << findMinDiff(test) << endl; // 输出1
    return 0;
}

补充说明 #

• 代码默认处理数组长度小于2的场景返回0，你可以根据业务需求修改为抛出异常或者其他返回值。
• 整体时间复杂度为O(nlogn)，空间复杂度为O(n)，符合要求。

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