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

问题描述：

给定一个数组arr，找到abs（arr [i] - arr [j]）为012的最大abs（i-j）。找出相差不超过k的两个元素之间的最大距离

了不少心思后，我想出了下面的算法，

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(n log n)用于排序+每一个元素我们做一个二进制搜索O(log n) + rangeQuery，O(log n)。整体时间复杂度为O(nlogn + n*2*logn)，这是渐近的O(nlogn)。

该方法是否正确？是否有可能制定一个线性时间解决方案？我尝试使用hashmaps，但很难找到线性解决方案。

我以前见过这个问题。像谷歌这样的公司的经典面试问题。 – IceArdor

答

对于一般情况，您的想法似乎有效。

对于元素均为整数的情况，您可以在Θ（n k）预期时间内执行此操作。如果k = 0（log（n）），this is a saving。如果k是常数，则这在n中是线性的。

放置在一个哈希表映射所有元素的每个元素é其位置在数组中我（如果有比单一ê更多，让你在散放在每个条目表覆盖前一个 - 没关系）。
对于每个元素Ë在我位置，和d = -k， - （K - 1），... 0，1，...，K，检查是否E + d位于散列表中。如果是这样，您可以从散列表中获得e + d的位置，比如j。
保留的最大距离的位置，你在第2

是不是theta（nk）伪多项式解？在那种情况下，O（n^2）效果更好？另外，如果k是一个常数，但它很大（数十亿的数量级），那么O（n^2）再也不会更好？ – harunrashid

这就是为什么我指定* k = o（log（n））*（注意使用小的o - 我甚至链接到定义）的条件。如果是这样的话，那么根据定义这将更有效率。例如，如果k = 3，那么它将从n的某个值开始更有效，如果k = 1B，那么它将从n的较大值开始更有效。我还在第一句话中说过，对于一般情况，您的原始解决方案是高效的解决方案。 –

啊，我误读了k = o（log（n））部分！谢谢！线性解决方案是不可能的？ – harunrashid

答

我想出了这一点：

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²）。如果存在线性算法，我很感兴趣

我不确定这是否可行。我们正在寻找阵列中距离最远的两个元素。排序会破坏原始索引的信息。还返回l [-1] - l [0]是最大差异，我们正在寻找距离！ – harunrashid

哦，马恩，我的坏 –

更改了代码。尽管如此，它仍然是N²最糟糕的情况。 –

答

发现这似乎有点被迫的“线性”的定义。我会以不同的方式处理。我们可以注意到函数距离d正在搜索最大值。因此，我们知道有下列组合： - DIST COUPLES COUNT

d = N-1的（a [0]，A [N-1]）1
d =正-2（a [0]，a [n-2]），（a [1]，a [n-1]）2
...
d = 1（A [0]，A [1]）...（A [N-2]，A [N-1]）n-1个

由于我们查询的最大我们将首先通过最大距离进行调查。所以我们有最好的情况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"); 
}

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

相关推荐