最大间隔问题

问题描述

给定n个实数x₁, x₂, x₃, … , x_n, 求这n个数在实轴上相邻2个数之间的最大间隔。假设对任何实数取整耗时O(1), 设计解最大间隙问题的线性时间算法。

算法设计

对于给定的n个实数x₁, x₂, x₃, … , x_n, 计算它们的最大间隙。

数据输入

输入数据由文件名为input.txt的文本文件提供，文件的第1行有1一个正整数n, 接下来1行中有n个实数x₁, x₂, x₃, … , x_n。

数据输出

将找到的最大间隔输出到文件output.txt

样例

输入：
5
2.3 3.1 7.5 1.5 6.3
输出：
3.2

算法实现分析

本问题可以运用鸽巢原理进行解答。其具体实现步骤如下：

1. 找出n个实数中的最大值n_max 和 最小值n_min
2. 申请n+1个盘子，并记录每一个盘子中的元素个数、上下界
3. 将[n_min, n_max]划分成n-1个等长区间，第一个盘子只放最小值，最后一个盘子只放最大值，剩余n-1个盘子用来存放n-2个数。很明显，必然至少有一个盘子没有存放任何数。因此，最大间隔存在于空盘子的两侧。
4. 线性查找出最大间隔。

实现代码

#include <iostream>
#include <fstream>
#include <cstring>
#include <math.h>

using namespace std;

#define infilePath "./input.txt"
#define outFilePath "./output.txt"


int main(int argc, char**argv)
{
    int Nums;
    float n_max;
    float n_min;

    ifstream infile;
    ofstream outfile;

    infile.open(infilePath, ios::in);
    outfile.open(outFilePath, ios::out);

    if (!infile.is_open())
        cout << "open file failure" << endl;
    if (!outfile.is_open())
        cout << "open file failure" << endl;

    while (infile >> Nums)
    {
        float * number = new float[Nums];
        float maxInterval = 0;

        //读入数据 并 找到最大值和最小值
        for (int i = 0; i < Nums; i++)
        {
            infile >> number[i];

            if (i == 0)
            {
                n_max = number[0];
                n_min = number[0];
                continue;
            }

            if (number[i]>n_max)
            {
                n_max = number[i];
            }
            if (number[i] < n_min)
            {
                n_min = number[i];
            }
        }

        //申请记录每一个盘子的元素个数和其上下界 第一个盘子 只放最小值 最后一个盘子只放最大值
        int* count = new int[Nums + 1];
        float* upperBound = new float[Nums + 1];
        float* lowerBound = new float[Nums + 1];

        for (int i = 1; i < Nums; i++)
        {
            count[i] = 0;
            upperBound[i] = n_min;
            lowerBound[i] = n_max;
        }

        count[0] = 1;
        count[Nums] = 1;
        upperBound[0] = n_min;
        lowerBound[0] = n_min;
        upperBound[Nums] = n_max;
        lowerBound[Nums] = n_max;

        //将n-2个数放入 n-1个盘子中
        for (int i = 0; i < Nums; i++)
        {
            if (number[i] == n_max || number[i] == n_min) continue;

            int index = floor((number[i] - n_min)*(Nums - 1) / (n_max - n_min)) + 1;   // 下标取值范围 1 到 n-1  

            if (number[i]>upperBound[index])
            {
                upperBound[index] = number[i];
            }
            if (number[i] < lowerBound[index])
            {
                lowerBound[index] = number[i];
            }
            count[index] ++;
        }

        //线性查找最大间隔 存在于count=0 的两侧
        for (int i = 1; i < Nums; i++)
        {
            int tmp;
            float gap;
            if (count[i]>0)
                continue;
            else
            {
                tmp = i;
                while (!count[i])
                    i++;
                gap = lowerBound[i] - upperBound[tmp - 1];
            }
            if (gap > maxInterval)
                maxInterval = gap;
        }

        //输出结果
        outfile << maxInterval<< endl;
    }

    //关闭文件
    infile.close();
    outfile.close();
}

测试结果

输入：
5
5.1 5.2 5.3 5.39 5.9
5
2.3 3.1 7.5 1.5 6.3
3
1.08 1.090 1.80
输出：
0.51
3.2
0.71