极差一个实际算法应用

Question

一个样本数据 1000个随机数.每组为20个数,问最多可以取出多少组要求: 极差不能小于90 (也就是这一组中的最大值减去最小值不能大于90)朋友们有没有好的算法呀..谢谢了..

Answer 1

先排序，记作 list
int index = 0;
while (index < 980)
{
    if (list[index + 19] - list[index] < 90)
    {
        // index - (index+19) 算1组
        index += 20;
    }
    else
    {
        ++index;
    }
}

Answer 2

我说一下我的大概想法
首先排序，按照大小
然后对排序之后的数组进行取值。
因为极差不能大于90，所以你取值的段必须遵循最后一个数字和第一个数字的差不能大于90
如果你的数组中存在超过20个的数字满足极差条件的话，那么就是一个数组，如果你的数组中不超过20个数字满足极差的条件，那么就不能是一个数组，你需要看下一个数字。
我说的数组是指你排序过后的，另外取值之后，你排序的数组需要将取出的数字去除掉。按照我的思路来看的话，你的程序有两种循环方式。
第一种，每次从第一个数字开始，两个指针，一直找到第一个满足条件的数字为止，找到之后，循环重新从第一个数字开始，找到的数组提出来。这样做的话，你的循环始终在找满足条件的第一个数组，找到一个就提出一个，并且重新开始找
第二种，从第一个数字开始，两个指针，找到一个数组，提出来，第一个指针指向你提出的数组的最后一个数字的后面一个数字，然后指针二从第一个指针当前位置+20的地方开始找，如果不满足继续移动指针一和指针二。这样做的话，你第一次循环可以提出来N个数组，N>=0。
对了，我说的两种都是两个指针，并且指针2的位置始终是指针1的位置+20，如果指针2到了你排序的数组的末尾，并且指针2的位置<=指针1的位置+19，那么你的数组中就没有符合极差的数组了。当然为了速度更快，你可以使用4个指针，左右开弓，但是这样来做的话，你的逻辑就相对复杂一些，比较难控制，需要你对你的算法的容错性有相当的自信。在稳定和效率之间做个权衡吧