#include <iostream>
using namespace std;
#include<vector>
//求最大间隙
//输入N 数字个数
//输入N 个数字输出结果
int main() {
double N;
int i;
cin >> N;
if (N < 2) {
return 0;
}
vector<double> array(N);
for ( i = 0;i < N; i++)
{
int a;
cin >> a;
array[i] = a;
}
//只有一个数没有间隙
/*对桶进行初始化*/
//每个桶的最大值初始化了一个最小数
//每个桶的最大值初始化了一个最小数
//这样是为了保证至少能够被array中的最大或最小数替换掉
//虽然定义了N个桶,但必然至少有一个桶是不会被用的
//记录每个桶每个桶被分到的数字
vector<int>count(0);
//记录每个桶中最大值
vector<double>max(N);
//记录每个分桶中最小值
vector<double>min(N);
/*找出梯队长度*/
// (MAX - MIN ) / (N-1)
double MAX = array[0], MIN = array[0];
for (i = 1; i < N; i++) {
if (array[i] > MAX) {
MAX = array[i];
}
if (array[i] < MIN) {
MIN = array[i];
}
}
// 数字全都一样的情况
if (MAX - MIN == 0) {
return 0;
}
double len = (MAX - MIN) / (N - 1);
/*把n个数放到n-1个桶中,必然至少一个桶没放数,至少一个,因为我定义了n个桶*,而又是按n-1划分的*/
int index;
for (i = 0; i < N; i++) {
index = (int)((array[i] - MIN) / len);
if (min[index] > array[i])
min[index] = array[i];
if (max[index] < array[i])
max[index] = array[i];
count[index]++;
}
/*计算最大间隙*/
int x, y;
double Gap = len, last, now;
for (i = 0; i < N - 1;) {
x = i;
last = max[x];
if (count[i + 1] == 0) {
while (count[++i] == 0);
y = i;
}
else {
y = i + 1;
}
now = min[y];
if (now - last > Gap) {
Gap = now - last;
}
i = y;
}
cout<<Gap<<endl;
system("pause");
return 0;
}
查了csdn说是越界,但是我也分配了空间了啊,访问max[0]没问题,一赋值就出错,这是为什么啊?
新手小白求帮助!!