题目描述
请输出数字序列的最大间隔。
请使用以下伪随机数生成函数 rand32 () 生成伪随机数
int seed ;
int rand(){ return((( seed = seed * 214013L + 2531011L) >> 16) & 0x7fff); }
int rand32(){undefined
return ((rand() << 16) + (rand() << 1) + rand() % 2);
}
Input Format
2个整数，n seed 其中 2<n<=20000000，seed为随机数种子。
Output Format
整数序列的最大间隔
Example
Input
2000000
1
Output
15737
注意：O(nlogn)以上的时间复杂度至少会有一个案例超时。
样例
输入:
1959000 4910
输出:
16709
?作为刚学数据结构的小白，刚看题时其实还是有点懵的。老师上课讲的散列（哈希）还没有完全搞明白，结果当天晚上12点前就要提交这道题，内心小崩~~~~主要当天课太多，很晚才回宿舍，我自知我能力有限，单靠自己想肯定是完不成了，所以就在CSDN上搜索了一下题目，虽然有的博主发过，但并没有太多讲解就直接上了代码。其实那时候挺崩溃的，虽然很不甘哈，但还是直接Ctrl+C、Ctrl+V了〔╯o╰〕。转天我研究了一下才决定写一写关于这道题的一些想法，既为了自己看着方便也为了以后有的同学理解。
（PS：说明一下，我理解这道题时既依靠了老师的提示，也依靠了网上博主的代码，源代码链接我放在下面。对于源代码我其实有一些意见不同的地方，所以我的代码和原作者的有些出入。也许是我理解不到位哈，如果大家有想法，欢迎在下面留言哦！但也请兄弟姐妹们不要太暴躁哈，毕竟关爱小白人人有责呀（＞▽＜）！！）
链接：https://blog.csdn.net/weixin_45964488/article/details/111604028
一、明确题目要求
说实话，一开始我并没有理解到底说的是什么意思。有的同学调侃：“题目说了要干什么，但又没完全说。”其实题目的意思是给定一个大小为n的数组（外部输入），将这n个数标在实轴上，问：分为的n-1段有界区间（另加两段无界的，那个就不用算啦）其中，哪一段最长。（如下图）
换句话说就是问将数组的n个元素排完序后，前一个数和后一个数的差（共n-1个）最大是多少。?
二、如何实现
知道了题目的要求，现在我们需要确定做什么。
需要做的就是排序和比较。
一般来讲我们首先想到的是先通过排序算法将数组排好序，之后再去通过循环去比较每个相邻数的差的大小，是个可行的办法。不过，我们要看一下题目中的一句话：
注意：O(nlogn)以上的时间复杂度至少会有一个案例超时。
现在，反观我们所有的八大排序算法，插排、快排、冒泡排、堆排等等，时间复杂度都不会低于O(nlogn)，所以我们需要寻找另一条路径。
这时候hash就登上了“历史舞台”。具体的哈希表（散列表）的概念及相关大家可以去自行搜索，这里就不赘述了。
运用hash算法我们可以将时间复杂度控制在O(n)层级上，可以说是性能极高的算法。不知道大家在看到一个比常规方法性能高得多的算法时是什么想法，我是感到震惊，同时又感到自己就是个大大的 fw (≧ ﹏ ≦)
咳咳，言归正传。具体是算法流程是这样：
? ? ? ? ? ? ? ? 找到数组中的最大、最小值? ? O(n) ?//一趟线性扫描 ?? ?
将有效范围均匀地划分为n-1段（桶）?? ?O(n) ?//相当于散列表 ??
? ? ? ???通过散列，将各点归入对应的桶?? ?O(n)? //寻找合适的哈希函数? ? ?
? ??? ? ? 在各桶中动态记录最大、最小值? ?O(n) ?//可能相同甚至没有 ?? ?
? ? ? ?算出相邻（非空）桶之间的“距离”?? ?O(n) ?//一趟遍历足矣 ?? ?
? ? ? ? ? ? ? ? ? ? ? ? ?最大的距离即maxgap? ? O(n)?
正确性：maxgap至少与（相邻的）两个桶相交
等价地，定义maxgap的点不可能属于同一个桶
其实整个核心流程就是要找到合适的散列函数，将大小相近的数分到相同的桶中（桶本质上就是数组，用来容纳大小相近的数），经过每个桶内数与桶间数的距离比较最后确定出最大的距离，即maxgap。
三、代码实现
现在我们就来逐步看一下代码的操作
首先说一点，题目中给出的随机数函数就是用来随机填充数组的,不用多想直接用就可以。
另外，上述功能的实现全部放在了一个函数里
int maxgap(int a[])?传入的是?main()?函数中用随机数函数生成的随机数数组。
1、找到数组中的最大、最小值
int amax = a[0], amin = a[0];
for (int i = 0;i < n;i++)
{
if (amax < a[i])amax = a[i];
if (amin > a[i])amin = a[i];
}
if (amax == amin)return 0;amax表示a数组中的最大值，amin大家也能猜到，用来表示数组中的最小值。
最后的 if 语句大家需要注意一下，如果整个数组的最大最小值是一样的，那么就可以直接下班退出啦，不过可以直接下班的好事还是少呀，唉 ∩﹏∩
有的同学会问这一步有什么用，真的是好问题，所以好问题得在后面说，嘿嘿
2、将有效范围均匀地划分为n-1段（n桶）//相当于散列表
bool* bucket = new bool[n];
for (int i = 0;i < n;i++)bucket[i] = 0;bucket[] 只是用来表示该桶是否为空，虽然后面我们要记录每个桶中的最大最小值，但是只要动态记录就可以了，并用不到静态储存，具体的后面会讲，所以这里将其设置成布尔数组就可以啦。
( PS：我参考的那个博主申请的数组大小是 n+1。但我认为即使是最极端的情况下，n个数也只是会被分入 n 个桶，所以申请 n 就可以了，并用不到 n+1。)
3、?通过散列，将各点归入对应的桶 ；在各桶中动态记录最大、最小值（原3、4步合并）
int* imax = new int[n];
int* imin = new int[n];
double gap = double(amax - amin) / (n - 1);
for (int i = 0;i < n;i++)
{
int index = int((a[i] - amin) / gap);
if (bucket[index] == 0)
{
imax[index] = a[i];
imin[index] = a[i];
bucket[index] = 1;
}
else
{
imax[index] = max(a[i], imax[index]);
imin[index] = min(a[i], imin[index]);
}
}imax[] 用于记录每个桶中的最大值，imin[]?则用于记录每个桶中的最小值 ，index表示将每个数归入的桶的下标。
我觉得这一段代码的关键是 gap 的计算与 index 的确定。当时我的疑问就是为什么要这么算。现在我来尝试解释一下。
首先，我们要将数组中的每个数归入桶中，而桶其实就是前面的 bucket[]，我们在申请数组时的下标只能是连续的从 0 到 n-1 ,而不可能是跳跃的下标。所以要想办法通过操作将每个数通过计算分入不同的桶，而且算出的下标(index)不能大于n-1。gap的计算方法大家可以看到，它实际上就是一个标尺，通过计算每个数与最小值的差与gap的倍数来确定进入哪个桶。最小的情况是 a[i] 等于amin，结果 index 为 0；最大情况是 a[i] 等于amax，结果index为 n-1，正好符合需求。【其实我认为这种处理方式大家可以记住，下此遇到类似的排序情况就可以直接使用了】
后面的代码大家基本上就可以看明白。就是动态存储了每个桶中的最大最小值，以及将非空的桶置为1。以上的过程就相当于进行了数据排序，只不过时间性能有了提升！强调一点就是注意gap是double 类型，因为是标尺还是越精确越好，而后面的index需要是整型，因为下标只能是整数。
（ PS：原博主申请的记录各桶最大最小值的数组大小都是n+1,但我觉的n就足够了，理由同上）
?4、算出相邻（非空）桶之间的“距离”?
int lastmax;
int maxgap = 0;
for (int i = 0;i < n;i++)
if (bucket[i] != 0)
{
lastmax = imax[i];
}
for (int i = 1;i < n;i++)
{
if (bucket[i] != 0)
{
int tem = max(imin[i] - lastmax, imax[i] - imin[i]);
maxgap = max(maxgap, tem);
lastmax = imax[i];
}
}?lastmax用于表示前一个桶的最大值。
声明maxgap用于存储最终结果，虽然代码里写的是初值为1，但我认为更应该设置为INT_MIN(即最小的整型数字)，因为我们也不确定是否有负数。但是设为0可以通过并且学校OJ并不识别INT_MIN,所以我这里就继续使用0了。
第一个for循环用于找到第一个非空桶，并将其中的最大值赋给lastmax。
第二个for循环就是要比较找出最大的差值，比较的三者是现在所处桶的最小值与前一桶的最大值的差、现在所处桶的最大值与最小值的差、以及maxgap本身。
（PS：原博主在第二个循环中的比较是下面那样的。但我认为所处桶内的最大最小的差不能被忽视，即使它们之间的距离可能较短，但还是必须要考虑的一点）
for (int i = 1; i <= n; i++)
{
if (hasNum[i])
{
maxGap = max(maxGap, (mins[i] - lastMax));
//cout << mins[i] << ' ' << lastMax << endl;
lastMax = maxs[i];
}
}
好啦，以上就是这道题的全部内容啦。这是我第一次写文章，总归有不足，不管是排版还是思路，亦或者能力上的缺陷也请各位同学们指出哈。凡事都是有第一次，第一次写不好，第二次一定会有进步。
蟹蟹大家啦！！！！！！！！
哦，差点忘了完整代码~~~
/*
请输出数字序列的最大间隔。
请使用以下伪随机数生成函数 rand32 () 生成伪随机数
int seed ;
int rand(){ return((( seed = seed * 214013L + 2531011L) >> 16) & 0x7fff); }
int rand32(){
return ((rand() << 16) + (rand() << 1) + rand() % 2);
}
*/
#include<iostream>
using namespace std;
int n,seed;
int rand()
{
return(((seed = seed * 214013L + 2531011L) >> 16) & 0x7fff);
}
int rand32()
{
return ((rand() << 16) + (rand() << 1) + rand() % 2);
}//随机数
int maxgap(int a[])
{
int maxgap = 0;
int amax = a[0], amin = a[0];
for (int i = 0;i < n;i++)
{
if (amax < a[i])amax = a[i];
if (amin > a[i])amin = a[i];
}//找到数组中的最大、最小值
if (amax == amin)return 0;
bool* bucket = new bool[n];
for (int i = 0;i < n;i++)bucket[i] = 0;//将有效范围均匀地划分为n-1段（n桶）//相当于散列表
int* imax = new int[n];
int* imin = new int[n];
double gap = double(amax - amin) / (n - 1);
for (int i = 0;i < n;i++)
{
int index = ((a[i] - amin) / gap);
if (bucket[index] == 0)
{
imax[index] = a[i];
imin[index] = a[i];
bucket[index] = 1;
}
else
{
imax[index] = max(a[i], imax[index]);
imin[index] = min(a[i], imin[index]);
}
}//通过散列，将各点归入对应的桶 ；在各桶中动态记录最大、最小值
int lastmax;
for (int i = 0;i < n;i++)
if (bucket[i] != 0)
{
lastmax = imax[i];
}
for (int i = 1;i < n;i++)
{
if (bucket[i] != 0)
{
int tem = max(imin[i] - lastmax, imax[i] - imin[i]);
maxgap = max(maxgap, tem);
lastmax = imax[i];
}
}//算出相邻（非空）桶之间的“距离”?
return maxgap;
}
int main()
{
cin >> n >> seed;
int* np = new int[n];
for (int i = 0;i < n;i++)
np[i] = rand32();
cout << maxgap(np);
system("pause");
return 0;
}