O(n)时间复杂度求相邻成绩最大差异：桶排序算法详解

有时，我们会关心相邻名次间成绩的差异，比如冠军与亚军差多少，第四名与第五名差多少等等。编写函数，计算模拟的成绩数组（均为非负整数，但是是无序的）中相邻的名次间成绩的最大差异（指按从高到低排序后，前一名较后一名相差的最大值）。显然，排序后再统计是一种方法，我们对时间效率有一定的要求：你能否在O(n)的时间和空间复杂度下完成该任务？你可以认为，数据数量少于2个时，差异认为是0。

输入样例：第一行是长度N，第二行是N个以空格分隔的非负整数。

5 2 6 8 3 15 输出样例：函数计算并返回有序化后，相邻的两名间最大的差异（第一名15，第二名8，差最大为7）。

7 函数接口定义： int fun ( int D[],int N );

一种实现方式是使用桶排序。首先找到成绩数组中的最大值和最小值，然后创建一个长度为最大值和最小值之差加1的桶数组。将成绩数组中的每个元素放入对应的桶中。最后遍历桶数组，找到相邻非空桶之间的最大差值即为所求。

具体步骤如下：

找到成绩数组中的最大值和最小值，分别记为max和min。
创建一个长度为max-min+1的桶数组，初始化为0。
遍历成绩数组，将每个元素放入对应的桶中。对于成绩数组中的元素D[i]，将其放入桶数组的索引为D[i]-min的位置。
遍历桶数组，找到相邻非空桶之间的最大差值。具体方法是记录前一个非空桶的索引prev，然后从prev+1开始遍历桶数组，找到下一个非空桶的索引cur。计算cur-prev-1并更新最大差值。
返回最大差值作为结果。

时间复杂度分析：遍历成绩数组需要O(n)的时间复杂度，创建桶数组和遍历桶数组的时间复杂度都是O(max-min+1)。因此，总的时间复杂度是O(n+max-min+1)。在最坏情况下，max-min=n-1，所以总的时间复杂度可以简化为O(n)。空间复杂度为O(max-min+1)，在最坏情况下也可以简化为O(n)。

具体实现如下：

#include <iostream>
#include <vector>
using namespace std;

int fun(int D[], int N) {
    if (N < 2) {
        return 0;
    }
    int maxScore = D[0];
    int minScore = D[0];
    for (int i = 1; i < N; i++) {
        if (D[i] > maxScore) {
            maxScore = D[i];
        }
        if (D[i] < minScore) {
            minScore = D[i];
        }
    }
    vector<int> bucket(maxScore - minScore + 1, 0);
    for (int i = 0; i < N; i++) {
        bucket[D[i] - minScore]++;
    }
    int prev = -1;
    int maxDiff = 0;
    for (int i = 0; i < bucket.size(); i++) {
        if (bucket[i] != 0) {
            if (prev != -1) {
                int cur = i;
                int diff = cur - prev - 1;
                if (diff > maxDiff) {
                    maxDiff = diff;
                }
            }
            prev = i;
        }
    }
    return maxDiff;
}

int main() {
    int N;
    cin >> N;
    int D[N];
    for (int i = 0; i < N; i++) {
        cin >> D[i];
    }
    int result = fun(D, N);
    cout << result << endl;
    return 0;
}

测试样例：

输入： 5 2 6 8 3 15 输出： 7