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

题目

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

分析

题目限制不能使用非基于比较的排序，也就是不允许使用桶排序的方法，但可以借鉴桶排序的思想，原数组有N个数，则创建N+1个桶，数组的最小值放在第0号桶里，数组的最大值放在最后一个桶里，然后遍历数组，桶内只放该区域的最大值和最小值。遍历到最后一定会有一个空桶，设置空桶的目的是为了排除同一桶内存在最大差值的问题（但说实话我还是没理解空桶放在这里的作用），只要比较非空的最小值，与前一个非空桶的最大值，求最大的差值就是答案。

// 给定数组，求排序之后相邻两个数的最大差值.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

int bucket(int number, int length, int min, int max)
{
	return(int)((number - min)*length / (max - min));
}
int Max_Gap(vector<int>array)
{
	int length = array.size();
	if (length == 0 || length < 2)
		return 0;
	int max_data = *max_element(array.begin(), array.end());
	int min_data = *min_element(array.begin(), array.end());
	if (max_data == min_data)
		return 0;
	vector<bool>hasnum(length + 1);
	vector<int>maxs(length + 1);
	vector<int>mins(length + 1);
	int bid = 0;
	for (int i = 0; i < length; i++)
	{
		bid = bucket(array[i], length, min_data, max_data);
		mins[bid] = hasnum[bid] ? min(array[i], mins[bid]) : array[i];
		maxs[bid] = hasnum[bid] ? max(array[i], maxs[bid]) : array[i];
		hasnum[bid] = true;
	}
	int res = 0;
	int lastmax = maxs[0];
	for (int i = 1; i <= length; i++)
	{
		if (hasnum[i])
		{
			res = max((mins[i] - lastmax), res);
			lastmax = maxs[i];
		}
	}
	return res;
}