<center>最大間隙問題
1.問題描述
? ?給定n個(gè)實(shí)數(shù),求這n個(gè)數(shù)在實(shí)數(shù)軸上相鄰2個(gè)數(shù)之間的最大間隙，假設(shè)對(duì)任何實(shí)數(shù)的向下取整運(yùn)算耗時(shí)
涮总，設(shè)計(jì)一個(gè)線性時(shí)間算法解題胸囱。（數(shù)據(jù)的輸入由input.txt文件中讀得，算出的結(jié)果存到output.txt文件中瀑梗。）
1.1 題目分析
- 問題求相鄰的最大間距烹笔，輸入又是無序的，如若先進(jìn)行排序抛丽，則排序的復(fù)雜度最少是
,不滿足線性時(shí)間復(fù)雜度要求谤职。所以只能另想他法。
- 問題聯(lián)想到組合數(shù)學(xué)中的插板問題亿鲜，將數(shù)字序列的上界和下界看成等差數(shù)列的首項(xiàng)和末項(xiàng)允蜈，每個(gè)公差的間距看成一個(gè)容器，根據(jù)等差數(shù)列的通項(xiàng)公式將每個(gè)數(shù)字放到容器中去蒿柳。
,所以數(shù)字散落在第
個(gè)容器里陷寝。去除最小值，還剩下
個(gè)數(shù)字其馏，分布在n個(gè)容器里凤跑，遍歷容器至少有個(gè)空容器，有空的存在說明有大間距存在叛复。
1.2 想法可行性分析
??按照等差數(shù)列的通項(xiàng)公式 仔引，這樣就可以求出任意數(shù)據(jù)
所在的位置
。我們構(gòu)建n個(gè)相鄰容器褐奥，每個(gè)容器的寬度是公差d咖耘，第一個(gè)容器的起點(diǎn)是給定數(shù)字序列的最小值，第n個(gè)容器的起點(diǎn)是這個(gè)數(shù)字序列的最大值撬码。
| 容器1 | 容器2 | 容器n | |
|---|---|---|---|
??當(dāng)把除去最小值之外的所有數(shù)字按照等差公式放入到相應(yīng)容器中時(shí)儿倒，由于有個(gè)數(shù)字，而容器卻有
個(gè)呜笑，必然存在至少有一個(gè)容器為空夫否。那么問題就轉(zhuǎn)換為在遍歷
個(gè)容器找尋其中最長(zhǎng)連續(xù)為空的容器。
2. 解題過程描述
2.1. 數(shù)據(jù)結(jié)構(gòu)
??要實(shí)現(xiàn)上面的想法叫胁，需要借助于數(shù)據(jù)結(jié)構(gòu)凰慈。需要構(gòu)建容器類，其中包括的成員變量包括：容器中數(shù)字的數(shù)量驼鹅，容器中數(shù)字的最大值微谓、最小值森篷。類中的方法最主要的就是放置數(shù)字到容器中，該方法需要完成的工作包括：數(shù)字的數(shù)量+1豺型；驗(yàn)證新放置的數(shù)字是否超過目前容器中數(shù)字的最值界限仲智，若有，則更新最值姻氨。
#include <iostream>
#include <vector>
#include <math.h>
//抽屜類中包括元素個(gè)數(shù)钓辆，上界，下界哼绑，也可以有上下界索引
template<typename T>
class maxGap{
private:
int m_elemCount;
T m_high;
T m_low;
public:
maxGap():m_elemCount(0)
,m_high(0.0)
,m_low(0.0){}
const T getHigh() const {return m_high;}
const T getLow() const {return m_low;}
const int getCount() const {return m_elemCount;}
void insertElem(T elem){
if(m_elemCount == 0){
m_low = elem;
m_high = elem;
}
else if(elem > m_high)
m_high = elem;
else if(elem < m_low)
m_low = elem;
m_elemCount ++ ;
}
};
2.2. 算法描述及復(fù)雜度分析
??題干中要求時(shí)間的復(fù)雜度是線性的岩馍，下面我們來闡述算法流程和分析其時(shí)間復(fù)雜度。算法過程中主要的步驟包括：讀取文件抖韩，截取數(shù)字蛀恩，放置數(shù)字到容器，遍歷容器找到最大間隙茂浮。
template<typename T>
T solveMaxGap(std::vector<T> arr){
int len = arr.size();
T max = getmax(arr);
std::cout<<"max:"<<max<<std::endl;
T min = getmin(arr);
std::cout<<"min:"<<min<<std::endl;
T dimen = (max - min)/(len - 1);
std::cout<<"dimen:"<<dimen<<std::endl;
T temp_high = arr[0] - arr[0];
T maxgap = 0;
T tempgap = 0;
int zeroPos = 0;
int zeroCount = 0;
maxGap<T> temp;
std::vector< maxGap<T> > container(100,temp);
container[len - 1].insertElem(max);//最大值放在len-1的位置双谆，非最值位于[0，len-2]
//將元素放入桶中
for(int i = 0 ;i < len; i++){
if(arr[i] != max && arr[i] != min){
int pos = floor((arr[i] - min )/ dimen);
// std::cout<<arr[i] <<"- "<< min<<"/"<<dimen <<":position:"<<pos<<std::endl;
container[pos].insertElem(arr[i]);
}
}
//遍歷桶席揽，找到最長(zhǎng)的連續(xù)空桶顽馋，或最大間隙
for(int i = 0;i < len ; i ++){
if(container[i].getCount() == 0)
{
zeroPos = I;
zeroCount ++;
}
else
{
if(zeroCount == 0)
continue;
else{
if(zeroPos - zeroCount < 0 ){
tempgap = container[zeroPos + 1].getLow() - min;
maxgap = (maxgap > tempgap)?maxgap:tempgap;
}
else{
tempgap = container[zeroPos + 1].getLow() - container[zeroPos - zeroCount].getHigh();
//std::cout<<"tempgap : "<<tempgap<<std::endl;
maxgap = (maxgap > tempgap)?maxgap:tempgap;
zeroCount = 0;
zeroPos = 0;
}
}
}
}
return maxgap;
}
??程序中所有的循環(huán)都不存在嵌套，只存在遍歷線性容器幌羞，時(shí)間復(fù)雜度為寸谜，程序滿足題目要求。
2.3. 算法結(jié)果驗(yàn)證
