【IT笔试面试题整理】最大间隔问题

【题目描述】给定n个实数x1,x2,…,xn,求这n个实数在实轴上相邻2个数之间的最大差值,要求设计线性的时间算法

【题目来源】百度

【题目分析】
由于要求要线性时间,所以不能使用排序,于是使用了一种类似桶排序的变形

【算法】
距离平均值为offset =(arrayMax - arrayMin) / (n - 1),
则距离最大的数必然大于这个值。
每个桶只要记住桶中的最大值和最小值,依次比较上一个桶的最大值与下一个桶的最小值的差值,找最大的即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
给定n个实数x1,x2,...,xn,求这n个实数在实轴上相邻2个数之间的最大差值,要求设计线性的时间算法
*/
/**
算法:
距离平均值为offset = (arrayMax - arrayMin) / (n - 1), 则距离最大的数必然大于这个值
每个桶只要记住桶中的最大值和最小值,依次比较上一个桶的最大值与下一个桶的最小值的差值
找最大的即可.
*/
#include <iostream>
#define MAXSIZE 100 //实数的个数
#define MAXNUM 32767
using namespace std;
struct Barrel
{
double min; //桶中最小的数
double max; //桶中最大的数
bool flag; //标记桶中有数
};
int BarrelOperation(double* array, int n)
{
Barrel barrel[MAXSIZE]; //实际使用的桶
int nBarrel = 0; //实际使用桶的个数
Barrel tmp[MAXSIZE]; //临时桶,用于暂存数据
double arrayMax = -MAXNUM, arrayMin = MAXNUM;
for(int i = 0; i < n; i++) {
if(array[i] > arrayMax)
arrayMax = array[i];
if(array[i] < arrayMin)
arrayMin = array[i];
}
double offset = (arrayMax - arrayMin) / (n - 1); //所有数的平均间隔
//对桶进行初始化
for(i = 0; i < n; i++) {
tmp[i].flag = false;
tmp[i].max = arrayMin;
tmp[i].min = arrayMax;
}
//对数据进行分桶
for(i = 0; i < n; i++) {
int pos = (int)((array[i] - arrayMin) / offset);
if(!tmp[pos].flag) {
tmp[pos].max = tmp[pos].min = array[i];
tmp[pos].flag = true;
} else {
if(array[i] > tmp[pos].max)
tmp[pos].max = array[i];
if(array[i] < tmp[pos].min)
tmp[pos].min = array[i];
}
}
for(i = 0; i <= n; i++) {
if(tmp[i].flag)
barrel[nBarrel++] = tmp[i];
}
int maxOffset = 0.0;
for(i = 0; i < nBarrel - 1; i++) {
if((barrel[i+1].min - barrel[i].max) > maxOffset)
maxOffset = barrel[i+1].min - barrel[i].max;
}
return maxOffset;
}
int main()
{
double array[MAXSIZE] = {1, 8, 6, 11, 7, 13, 16, 5}; //所需处理的数据
int n = 8; //数的个数
//double array[MAXSIZE] = {8, 6, 11};
//int n = 3;
int maxOffset = BarrelOperation(array, n);
cout << maxOffset << endl;
return 0;
}

【参考资料】
http://topic.csdn.net/u/20101015/15/1eaab1a3-4432-4f17-be8b-1716fef3e59c.html
http://blog.csdn.net/livelylittlefish/archive/2008/03/23/2209537.aspx

坚持原创技术分享,您的支持将鼓励我继续创作!