1

A[1..n] には正の要素しかありません。

O(n) の解決策が 1 つあります。

B = new Array()

for i=1 to n
    B[i] = 3A[i]-7

C = merge(A,B) such that C is also sorted

for i=1 to n-1
    if (C[i] == C[i+1])
        return TRUE

return FALSE

それを行うO（1）の方法は何ですか？ところで、私は (おそらく間違った) スケッチを持っています。そこでは、2 つのスキャンラインを使用して見つけることができると書かれていますが、それも理解できません。

4

2 に答える 2

2

2 つのポインターを維持しながら、配列を左から右にスキャンしbますa。以下は疑似コードの実装です (実行可能な Python でもあります)。

def find(l):
  i, j = 0, 0
  while i < len(l) and j < len(l):
    b = l[i]
    a = 3 * b - 7
    while j < len(l) and l[j] < a:
      j += 1
    if j < len(l) and l[j] == a:
      return i, j
    i += 1
  return None

l = [1, 3, 5, 8, 10, 27, 45]
print find(l)

これは O(1) 空間と O(n) 時間です (要素を 2 回以上見ることはないため)。

于 2013-01-26T17:07:41.807 に答える
2

2 つのインデックス i1 と i2 を、並べ替えられた配列の先頭に初期化します。

今ループ：

i1 の値を取得し、3b-7 を計算します。

値が >= 検索値になるまで、i2 から順方向に検索します。= の場合、2 つの整数が見つかりました。> の場合は、i1 を進めてループします。

于 2013-01-26T16:59:49.113 に答える