查找排序数组值之间的最大差异

finding the biggest difference between sorted array values

本文关键字：之间 排序 数组 查找      更新时间：2023-09-26

我有一个像这样的数组…

var array = array(1,4,7,8,12,15);

数组中的值将始终是整数，并且总是递增，或者可以与前一个相同，但至少不会变小。

现在我想循环遍历数组并找出哪个"步骤"之间的最大差异，所以在我的例子中，这将是数组键4&5，因为从8-12 == 4…但也有可能这将是具有相同值的多个步骤，假设我的数组是这个。

var array = array(1,5,7,8,12,15);

则为0&1和4&5....

我正在寻找一个函数，可以返回我这个…哦，必须是纯果汁……

我希望有人能帮助我。

我不确定你到底想要什么。但是如果你想要最大的跳跃:

var max=0;
for (i=1; i<array.length; i++)
    max = Math.max(max,array[i]-array[i-1]);

如果您想要最大跳变发生的第一个位置:

var max=0;
var firstLoc=0;
for (i=1; i<array.length; i++)
{
    curJump = array[i]-array[i-1];
    if (curJump > max) 
    {
        firstLoc = i;
        max = curJump;
    }
}

如果您想要此跳转发生的最后位置:

var max=0;
var lastLoc=0;
for (i=1; i<array.length; i++)
{
    curJump = array[i]-array[i-1];
    if (curJump >= max) 
    {
        lastLoc = i;
        max = curJump;
    }
}

如果你想要一个包含发生最大跳跃的所有位置的数组:

var max=0;
var locs = [];
for (i=1; i<array.length; i++)
{
    curJump = array[i]-array[i-1];
    if (curJump == max)
    {
        locs.push(i);
    } else if (curJump > max)
    {
        locs = [i];
        max = curJump;
    }
}

函数式方法使用简单的纯函数和内置函数来完成一些繁重的工作:

var array = Array(1,5,7,8,12,15);
//get differences:
var diffs=array.map(function(a,b,c){
 return a - (c[b-1]||0);
},{});
//find max diff and collect elements:
var rez=diffs.map(function(a,b){return a==this && [b-1, b]; }, 
                   Math.max.apply(0, diffs)
            ).filter(Boolean);
//display the findings:
alert(rez.join("|")) //shows: 0,1|3,4

当我完成的时候，我总是很惊讶，我没有看到任何本地变量或条件被使用…

蛮力解决方案是按顺序遍历数组，并查看从a[i]到[i+1]的差异。如果大于max，则将max设置为此值。

也可以使用二进制搜索，因为数组是排序的。

相关文章：