ソートされた配列にA [i] = 2A [j]が存在するかどうかを確認します。

Question

この質問に似た質問があります。少し修正してcheck if there exists a[i] = 2*a[j] in an unsorted array a?です。

入力は、昇順で並べ替えられたn個の正の数の配列A [1 ... n]です。

問題は、A [i] = 2A [j]となるようなインデックスiとjのペアがあるかどうかを確認することです。

設計し、この問題のためにO（N）時間インプレースアルゴリズムを分析

Iの比較を介して補助データ構造およびループ内のすべての要素の二重を記憶することができれば問題は簡単であろう値を元の配列値に戻しますが、インプレース仕様ではそれが禁止されています。私が思いつくことができる最高のものはO（nlogn）です。n個の要素のそれぞれについて、その要素の2倍のバイナリ検索を行いますが、私の頭をもっと速く包むことはできません。 Aとして

Answer 1

ので、増加している：

1. i > j
2. をA[i] > 2 * A[j]場合A[i] < 2 * A[j]場合、k <= jと(i, k)が有効なペア
3. ないが、k <= iと(k, j)は

有効なペアではありませんアルゴリズムは次のようなPythonコードになります：

def foo(a): 
    i = 1 
    j = 0 
    n = len(a) 

    while n > i > j: 
     if a[i] == 2 * a[j]: 
      print("a[{}] = 2 * a[{}]".format(i, j)) 
      i += 1 
     elif a[i] < 2 * a[j]: 
      i += 1 
     else: 
      j += 1 
      if i == j: 
       i += 1 

Answer 2

擬似コード：

i = 1 
j = 1 
while j <= n and 2 * A[i] <> A[j] 
    if 2 * A[i] < A[j] 
     i = i + 1 
    else /* 2A[i] is greater than A[j] */ 
     j = j + 1 
if j <= n 
    print i, j 

下部要素の2A [i]が< A [j]の溶液が間隔で置くことができれば、このアルゴリズムは、以下の特徴

1. を使用して[ 2A [i]> A [j]ならば、上の要素の解は[j + 1、...、n]になければならない。

ループは、最大で2つのN手順をとり、したがって、このアルゴリズムは、O（N）手順を必要とします。