桶相邻找最大值

桶找相邻差值最大

定一组无序数据，输出排序过后的相邻两个数字最大的差值 分析：

利用桶来找最大差值，有n个数，就找n+1个桶，必定有一个桶为空，这样就排除了同一个桶差值最大的可能性，但没排除相邻桶差值最大的可能性，找两个数组，一个记录每个桶中的数字的最大值，一个记录每个桶中的数字的最小值，根据最小值减上一个桶中的最大值再来找差值最大的 需要注意的是，只有桶中有数字才看该桶最大值和最小值

#include<iostream> 
#include<cstring>
using namespace std;
int bucket(int a ,int min ,int max, int len);
int sub(int* a,int len);
int sub(int* a,int len)
	{
		int Max=0;
		int Min=0;
		
		for (int k=0;k<len;k++)
		{
			Max=max(Max,a[k]);
			Min=min(Min,a[k]);
		}
		if (Max== Min) 
		{
			return 0;
		}
		bool* hasnum = new bool[len+1];
		int* maxs = new int [len+1];  //初始桶都为空 
		int* mins = new int[len+1];
		memset(hasnum,0,len+1);
		for(int k=0;k<len;k++)
		{
			int bid = bucket(a[k],Min, Max,len);
			mins[bid] = hasnum[bid] ? min(mins[bid],a[k]) : a[k];
			maxs[bid] = hasnum[bid] ? max(mins[bid],a[k]) : a[k];
			hasnum[bid] = true;
	    }
	    int lastmax = maxs[0];
	    int i=1;
	    int res = 0;
//	    for(int k=0;k< len;k++)
//	    {
//	    	cout<< k<<"  "<< mins[k]<<"  "<< maxs[k]<<"  "<< hasnum[k]<< endl;
//		}
//		
//		
//		cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
	    for(;i<=len;i++)
	    {
	    	if (hasnum[i]) //只有桶中有数字才比较
	    	{
	    	res = max(mins[i] - lastmax,res);
	    	lastmax = maxs[i];
	    	cout<<res<<endl; 
	        }
		}
	return res;
	}

int bucket(int a ,int min ,int max, int len)  //放入那个桶的捅号 
{
	return (int) ((a-min) * len /(max-min));
}

int main()
{
	int* a = new int[11]{12,5,3,8,22,8,51,9,73,52};
	cout<<sub(a,10)<<endl;
}