题目描述

给定一个数组， 求如果排序之后， 相邻两数的最大差值， 要求时间复杂度O(N)， 且要求不能用非基于比较的排序。

解法1：暴力法

题目要求时间复杂度为O（N），这意味着我们不能用基于比较的排序方法对数组做排序，因为最快也是O（NlogN）的，但还是做了一下。
方法就是排序了之后用后一个数减前一个数，更新maxGap的值就好了

解法2：利用桶的思想但不排序

这里，数组有N个数，就分N+1个桶，整个解法并不涉及排序
用三个数组记录每个桶的信息（最大值、最小值、是否有数）
最后，利用解法1的思想，求出所有当前桶的最小值和左边桶的最大值之差的最大值，即maxGap

测试结果及代码

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
using namespace std;

void printVector(vector<int> A) {
    for (const auto &i : A) {
        cout << i << " ";
    }
}

void Swap(int &x, int &y) {
    int t = x;
    x = y;
    y = t;
}

void compare(vector<int> &a) {
    int maxGap = INT_MIN;
    if (a.size() < 2) {
        cout << a[0] << " ";
        maxGap = 0;
    }
    else {
        sort(a.begin(), a.end());
        printVector(a);
        for (int i = 1; i < a.size(); ++i) {
            int gap = a[i] - a[i - 1];
            if (gap > maxGap)
                maxGap = gap;
        }
    }
    cout << "，相邻元素的最大差值为：" << maxGap << endl;
}

int getBucketID4num(int num, int len, int min, int max) {
    return static_cast<int>((num - min) * len / (max - min));
}

// 用了桶的概念但没有用桶排序
int maxGap(vector<int> &v) {
    int sz = v.size();
    if (sz < 2)
        return 0;
    int minValue = INT_MAX;
    int maxValue = INT_MIN;
    auto biggest = max_element(v.begin(), v.end());
    auto smallest = min_element(v.begin(), v.end());
    minValue = *smallest;
    maxValue = *biggest;
    if (maxValue == minValue)
        return 0;
    // N个数设置N+1个桶
    vector<bool> hasNum(sz + 1);
    vector<int> maxs(sz + 1);
    vector<int> mins(sz + 1);
    int bucket_id = 0;
    for (int i = 0; i < sz; ++i) {
        bucket_id = getBucketID4num(v[i], sz, minValue, maxValue);
        if (hasNum[bucket_id]) {
            mins[bucket_id] = min(v[i], mins[bucket_id]);
            maxs[bucket_id] = min(v[i], maxs[bucket_id]);
        } else {
            maxs[bucket_id] = mins[bucket_id] = v[i];
        }
        hasNum[bucket_id] = true;
    }
    int res = 0;
    int lastMax = maxs[0];
    // 从1号桶开始，如果它是空的，直接跳下一个数
    // 如果是非空的，找非空桶左边最近的非空桶的最大值和当前非空桶的最小值
    for (int i = 1; i <= sz; ++i) {
        if (hasNum[i]) {
            res = max(res, mins[i] - lastMax);
            lastMax = maxs[i];
        }
    }
    return res;
}

void test(vector<int> &a) {
    cout << "，相邻元素的最大差值为：" << maxGap(a) << endl;
}

bool isEqual(int A[], int B[], int N) {
    for (int i = 0; i < N; ++i) {
        if (A[i] != B[i])
            return false;
    }
    return true;
}

int main (int argc, char* argv[]) {

    srand(time(NULL));
    // const int size = 5;           // 随机生成的数组大小
    const int test_time = 120;      // 测试次数
    vector<int> a;
    vector<int> tmp1;
    vector<int> tmp2;


    for (int cnt = 0; cnt < test_time; ++cnt) {
        int N = rand() % 15 + 1;
        cout << "第 " << cnt << " 次生成：";
        for (int i = 0; i < N; ++i) {
            a.push_back(rand() % 20 + 1);
            cout << a[i] << " ";
        }
        cout << endl;
        tmp1 = a;
        tmp2 = a;
        cout << "第 " << cnt << " 次对比：";
        compare(tmp1);
        // printVector(tmp1);

        cout << "第 " << cnt << " 次测试：";
        printVector(tmp2);
        test(tmp2);
        
        cout << endl;
        a.clear();
        tmp1.clear();
        tmp2.clear();
    }
    return 0;
}