java - 查找数组中的数字

Question

下面这个问题有O(n)效率的解法吗？

You need to find a cell in an array such that all of the numbers before it are lower than it, and all the numbers after it are higher than it. You should ignore first and last cells.

例如，考虑以下列表:

1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11

在这种情况下，答案将是索引 5 处的数字 7。

Answer 1

这是一个 O(n)，Python 中的一次性解决方案。移植到 Java 很简单:

import random
A = [random.randint(1, 10) for i in range(0, 5)] # Generate list of size 5.
max_seen = A[0]
candidate = None
for i in range(1,len(A)):
  if candidate is None:
    if A[i] > max_seen:
      candidate = i
  else:
    if A[i] <= A[candidate]:
      candidate = None
  max_seen = max(max_seen, A[i])

print("Given %s " % (A,))
if candidate is not None and candidate != len(A)-1: # Ignore the last element as per spec.
  print("found: value=%d; index=%d\n" % (A[candidate], candidate))
else:
  print("not found")

您需要运行几次才能生成实际满足条件的列表。

---

描述

重述目标:找到数组 A 中元素的索引 i 使得 所有 A[j], j < i => A[j] < A[i] 和所有 A[k], k > i => A[k] > A[i]。第一个这样的元素是一个这样的元素，所以我们只找到第一个。

给定一个索引x，如果x满足上述条件则A[x] > A[0..x-1]且A[x ] < A[x+1..A.length]。对于给定的 x，验证这两个约束就足够了。注意 A[x] > A[0..x-1] <=> A[x] > max(A[0..x-1])。所以我们保持到目前为止看到的最大值，找到满足条件 1 的第一个 x 并遍历数组验证条件 2 是否满足。如果条件 2 从未被验证，我们知道下一个可能的候选者超出了当前索引 y，因为 A[x..y-1] > A[x] => A[y ] < A[x..y-1]，并且大于目前看到的最大值。