1

A[1..n] 只有正元素。

我有一个 O(n) 的解决方案：

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) 的方法是什么？顺便说一句，我有一个（可能是错误的）草图，上面说我们可以使用两条扫描线找到它，但我也不明白。

4

2 回答 2

2

将两个索引 i1 和 i2 初始化为已排序数组的开头。

现在循环：

获取 i1 处的值，并计算 3b-7。

现在从 i2 向前搜索，直到值 >= 搜索值。如果是=，你已经找到了这两个整数。如果是 > 则推进 i1 并循环。

于 2013-01-26T16:59:49.113 回答
2

从左到右扫描数组，维护两个指针：一个指向当前候选 for b，一个指向当前候选 for 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) 时间（因为它从不超过两次查看元素）。

于 2013-01-26T17:07:41.807 回答