ソート後の配列隣接要素間の最大差

題目説明:配列を与えて、もし並べ替えた後に、隣り合う2つの数の最大の差を求めるならば、時間の複雑度O(N)を要求して、しかも比較に基づく並べ替えを使うことができないことを要求します.
思想:バケツのソートに基づく基本思想.n+1バケツに分け,まず最小値と最大値をそれぞれ1バケツ目と最後のバケツに置き,残りのn−1バケツを配列の最大値と最小値で平均した.配列要素が2より大きい場合、並べ替え後の隣接要素の最大差は同じバケツ内に存在しないに違いないので、各バケツ内の最大値と最小値と、そのバケツ内に要素があるかどうか(1はある、0はない)を記憶して、複数のバケツを巡り、後のバケツの最小値と前のバケツの最大値との差を求めて、最大値を返します.すなわち、最終的に求められる結果である.このときの時間複雑度はO(n)であり,比較に基づくソートではない.

/*
      ，       ，         ，
        O(N)，              
*/

#include
#include
#include
#include
#include
#include
#include
using namespace std;

int maxGap(int *nums);
int bucket(long num, long len, long min, long max);
int comparator(int *nums);
int *generateRandomArray(int maxSize, int maxValue);
int *copyArray(int *arr);
void printArray(int *arr);

//       O(N)，         。
int maxGap(int *nums){
    int length = _msize(nums) / sizeof(int);
    if (nums == NULL || length < 2) {//           2，   0
        return 0;
    }
    int Min = INT_MAX;
    int Max = INT_MIN;
    for (int i = 0; i < length; i++) {
        Min = min(Min, nums[i]);
        Max = max(Max, nums[i]);
    }
    if (Min == Max) {
        return 0;
    }
    int *hasNum = new int[length + 1];
    int *maxs = new int[length + 1];
    int *mins = new int[length + 1];
    for (int i = 0; i < length + 1; i++){
        hasNum[i] = 0;//0         ，      max min 
    }

    int bid = 0;
    for (int i = 0; i < length; i++) {
        bid = bucket(nums[i], length, Min, Max);
        mins[bid] = hasNum[bid] ? min(mins[bid], nums[i]) : nums[i];
        maxs[bid] = hasNum[bid] ? max(maxs[bid], nums[i]) : nums[i];
        hasNum[bid] = 1;//1         max min 
    }

    int res = 0;
    int lastMax = maxs[0];
    int i = 1;
    for (; i <= length; i++) {
        if (hasNum[i]) {
            res = max(res, mins[i] - lastMax);
            lastMax = maxs[i];
        }
    }
    return res;
}

//          
int bucket(long num, long len, long min, long max){
    return (int)((num - min) * len / (max - min));
}

//        ，          
int comparator(int *arr){
    if(arr == NULL && _msize(arr)/sizeof(int) < 2)//           2，   0
        return 0;
    vector<int> temp;
    for(int i = 0; i < _msize(arr)/sizeof(int); i ++)
        temp.push_back(arr[i]);
    sort(temp.begin(),temp.end());
    for(int i = 0; i < temp.size(); i ++)
        arr[i] = temp[i];
    int gap = INT_MIN;
    for(int i = 1; i < temp.size(); i ++)
        gap = max(gap, arr[i] - arr[i - 1]);
    return gap;
}


int *generateRandomArray(int maxSize, int maxValue){
    srand((unsigned)time(NULL));
    int length = (int)(rand()%maxSize+1);
    int *arr = new int[length];
    for(int i = 0; i < length; i ++){
        arr[i] = (int)(rand()%maxValue);
    }
    return arr;
}

int *copyArray(int *arr){
    if(arr == NULL)
        return NULL;
    int *res = new int[_msize(arr)/sizeof(int)];
    for(int i = 0;i < _msize(arr)/sizeof(int); i ++)
        res[i] = arr[i];
    return res;
}

bool isEqual(int *arr1, int *arr2){
    if((arr1 == NULL && arr2 != NULL) || (arr1 != NULL && arr1 == NULL))
        return false;
    if(arr1 == NULL && arr2 == NULL)
        return true;
    if((_msize(arr1)/sizeof(int)) != (_msize(arr2)/sizeof(int)))
        return false;
    for(int i = 0; i < _msize(arr1)/sizeof(int); i ++){
        if(arr1[i] != arr2[i])
            return false;
    }
    return true;
}

void printArray(int *arr){
    if(arr == NULL)
        return;
    for(int i = 0; i < _msize(arr)/sizeof(int); i ++)
        cout<" ";
    cout<int main()
{
    int testTime = 50;
    int maxSize = 100;
    int maxValue = 100;
    bool succeed = true;
    for(int i = 0; i < testTime; i ++){
        int *arr1 = generateRandomArray(maxSize, maxValue);
        int *arr2 = copyArray(arr1);
        if(maxGap(arr1) != comparator(arr2)){
            succeed = false;
            break;
        }
    }
    cout<"Nice!" : "Fucking Fucked!")<int *arr = generateRandomArray(maxSize, maxValue);
    cout<<"       ："<cout<<"          gap ："<return 0;
}