找出两个相差不超过k的元素之间的最大距离

Question

给定一个数组arr，求最大abs（i-j），使abs（arr[i]-arr[j]）

经过深思熟虑，我想出了以下算法，

1) Create a new array of pair<arr[i], i> (say arrayIndexPairs)
2) Sort this arrayIndexPairs based on the array value (first of pair).
3) Build a segment tree on the index (second of pair) with the arrayIndexPairs so that we can answer range max queries
4) for i <- 0 to n-1
    4.1) rightIndex = Binary search the array values (first of pair) for ceil(arrayIndexPairs[i].first) in the interval [i+1, n-1]
    4.2) int maxIndex = rangeQueryForMax(i+1, rightIndex)
    4.3) result = max(result, maxIndex - i);
return result

对于每个元素的排序，我们进行二进制搜索的复杂性是O（log n），O（log n）rangeQuery，O（log n）。总体时间复杂度为O（nlogn*2*logn），是渐近的O（nlogn）。

这种方法正确吗？是否有可能制定线性时间解决方案？我尝试使用哈希图，但发现很难得出线性解决方案。

Answer 1

这似乎有点强迫“线性”的定义。我会用另一种方式。我们可以注意到函数距离d正在搜索最大值。因此我们知道有以下组合：-距离对计数

>

d=n-1（a[0]， a[n-1]）1

d=n-2（a[0]，a[n-2]），（a[1]，a[n-1]）2

由于我们搜索最大值，因此我们将首先研究最大距离。所以我们有最好的情况O（1），最坏的情况是从1到n-1=（n-1）*（n/2）=O（n2）的总和。平均我期望更好的性能，因为它可以非常有效地实现。
这里是C实现：

#include "stdio.h"
#include "stdlib.h"
#define ARRAYSIZE 10000

int find_dist(int * result, const int *array, int n,int k )
{
  int i,j,ti;
  for (i=n-1;i>0;i--)
  { 
     ti=i;       
     for (j=0;ti< n ; j++,ti++)
        if (abs(array[j]-array[ti])<=abs(k))
            {
                result[0]=j;
                result[1]=ti;
                return 1;
            }
   }
return 0;
}

int main()
{
  int array[ARRAYSIZE],result[2],i;
  for (i=0;i<ARRAYSIZE;i++)
    {
        array[i]=rand()%1000;
        //printf("%d ",array[i]);
    }
  if (find_dist(result,array,ARRAYSIZE,3))
    printf ("\n%d %d\n",result[0],result[1]);
  else
    printf ("No items match requirement\n");
 }

Answer 2

我想到了这个：

def find_max_abs(l, k):
    for lenght_of_interval in range(len(l), 1, -1):
        for start_of_interval in range(0, len(l) - lenght_of_interval + 1):
            if abs(l[start_of_interval] - l[start_of_interval + lenght_of_interval - 1]) <= k:
                return lenght_of_interval - 1

应该可以很好地工作，但它不是线性的（最坏的情况是N²）。我对线性算法是否存在感兴趣

Answer 3

就一般情况而言，你的想法似乎很有效。

对于元素都是整数的情况，可以在Θ（n k）预期时间内完成。如果k=o（log（n）），则这是一个保存。如果k是一个常数，这在n中是线性的。

>

将所有元素放置在一个哈希表中，将每个元素e映射到其在数组i中的位置（如果有多个e，则让您放置在哈希表中的每个条目覆盖上一个条目-这无关紧要）。

对于位置i处的每个元素e，d=-k，-（k-1）。。。0, 1, ... k、 检查哈希表中是否有e d。如果是这样的话，那么就得到了哈希表中的e d的位置，比如j。

保留在2中找到的最大距离的位置。