maxgap 问题

2019-03-22 本文已影响0人彳亍cium

<center>最大间隙问题

1.问题描述

给定n个实数 $x_1,x_2 ,x_3 \cdots x_n$ ,求这n个数在实数轴上相邻2个数之间的最大间隙，假设对任何实数的向下取整运算耗时 $O(1)$ ，设计一个线性时间算法解题。（数据的输入由input.txt文件中读得，算出的结果存到output.txt文件中。）

1.1 题目分析

问题求相邻的最大间距，输入又是无序的，如若先进行排序，则排序的复杂度最少是 $O(nlogn)$ ,不满足线性时间复杂度要求。所以只能另想他法。
问题联想到组合数学中的插板问题，将数字序列的上界和下界看成等差数列的首项和末项，每个公差的间距看成一个容器，根据等差数列的通项公式将每个数字放到容器中去。 $a_n = a_1 +(n-1)d$ ,所以数字散落在第 $0 \sim n-1$ 个容器里。去除最小值，还剩下 $n-1$ 个数字，分布在n个容器里，遍历容器至少有个空容器，有空的存在说明有大间距存在。

1.2 想法可行性分析

按照等差数列的通项公式 $(m-1)= \frac{a_m- a_1}{d}$ ，这样就可以求出任意数据 $a_m$ 所在的位置 $\{(m-1) \subset \{ 0,1,2 \cdots n-1 \}\}$ 。我们构建n个相邻容器，每个容器的宽度是公差d，第一个容器的起点是给定数字序列的最小值，第n个容器的起点是这个数字序列的最大值。

容器1	容器2	$\cdots \cdots$	容器n
$min \sim min+d - 1$	$min+d\sim min+2d -1$	$\cdots \cdots$	$min+(n-1)d \sim min+nd -1$

当把除去最小值之外的所有数字按照等差公式放入到相应容器中时，由于有 $n-1$ 个数字，而容器却有 $n$ 个，必然存在至少有一个容器为空。那么问题就转换为在遍历 $n$ 个容器找寻其中最长连续为空的容器。

2. 解题过程描述

2.1. 数据结构

要实现上面的想法，需要借助于数据结构。需要构建容器类，其中包括的成员变量包括：容器中数字的数量，容器中数字的最大值、最小值。类中的方法最主要的就是放置数字到容器中，该方法需要完成的工作包括：数字的数量+1；验证新放置的数字是否超过目前容器中数字的最值界限，若有，则更新最值。

#include <iostream>
#include <vector>
#include <math.h>
//抽屉类中包括元素个数，上界，下界，也可以有上下界索引
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. 算法描述及复杂度分析

题干中要求时间的复杂度是线性的 $O(n)$ ，下面我们来阐述算法流程和分析其时间复杂度。算法过程中主要的步骤包括：读取文件，截取数字，放置数字到容器，遍历容器找到最大间隙。

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]);
        }
    }

    //遍历桶，找到最长的连续空桶，或最大间隙
    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;

}

程序中所有的循环都不存在嵌套，只存在遍历线性容器，时间复杂度为 $O(n)$ ，程序满足题目要求。

2.3. 算法结果验证

result.png