kを超えない2つの要素間の最大距離を求める

Question

配列arrが与えられた場合、abs（arr [i] - arr [j]）< = kとなる最大abs（i-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) + rangeQuery、O(log n)を行うすべての要素のソート+のためO(n log n)です。全体的な時間の複雑さは、漸近的にであり、これは漸近的にO(nlogn)である。

アプローチは正しいですか？線形時間解を定式化することは可能ですか？私はハッシュマップを使ってみましたが、リニアソリューションに到達するのは非常に難しいと感じています。

Answer 1

一般的な場合、あなたの考えは効率的に見えます。

要素がすべて整数の場合は、Θ（n k）予定時刻で行うことができます。 k = 0（log（n））,this is a saving。 kが定数の場合、nでは線形です。

1. 置き、ハッシュ・テーブル・マッピング内のすべての要素の配列内の位置に各要素電子私（シングル電子以上がある場合、あなたはハッシュに置く各エントリを聞かせて前のテーブルを上書きする - それは問題ではない）。各要素Eについて

2. 位置におけるI、及びD = -k、 - （k - 1）E + Dの場合、...、0,1、...をK、チェックはハッシュテーブルにあります。その場合、ハッシュテーブルからe + dの位置、たとえばjの位置があります。

3. は、あなたがビットが「線形」の定義を強制的に思える2.

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

で見つかった最大距離の位置を保持します。 私は別のやり方でアプローチします。関数距離dが最大値を探索していることがわかります。 だから、以下の組み合わせがあることを知っている： - DISTカップルは

• D = N-1（[0]、[N-1]）1つの

• D = NのCOUNT -2（a [0]、a [n-2]）、（a [1]、a [n-1]）2

• ...
• D = 1（[0]、[1]）...（[N-2]、[N-1]）我々は、最大N-1

検索以来最初に最大距離で調べる予定です。したがって、最悪の場合、1からn-1 =（n-1）*（n/2）= O（n2）の合計が最良の場合O（1）を有する。 平均的には、パフォーマンスが非常に効率的に実装できるため、平均的なパフォーマンスが期待されます。
ここでは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"); 
}