在数组中查找数字

这是Python中的一个O（n），一次性解决方案。移植到 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] >最大值（A[0..x-1]）。因此，我们保持到目前为止看到的最大值，找到第一个满足条件1的x，并循环访问数组，验证条件2是否满足。如果条件 2 从未得到验证，我们知道下一个可能的候选项超出了当前索引 y，因为 A[x..y-1] > A[x] => A[y] < A[x..y-1]，并且大于到目前为止看到的最大值。

是的，它当然可以及时完成。下面有几种方法。O(n)

第一个对于查找所有候选单元格更有用。单次传递数据，为每个单元格设置两个额外的项目，从而获得空间（可以通过交换时间空间来解决不平凡数量的优化问题）。O(n)O(n)

您需要为每个单元格计算的两个项目是左侧的最大值和右侧的最小值。第一个传递为所有单元格设置这些项目，并在末尾没有意义的地方设置该项目（显然是伪代码）：

# Set current values.

highLeftVal = cell[0]
lowRightVal = cell[cell.lastIndex]

# For running right and left through array.

rightIdx = cell.lastIndex
for each leftIdx 1 thru cell.lastIndex inclusive:
    # Left index done by loop, right one manually.

    rightIdx = rightIdx - 1

    # Store current values and update.

    highLeft[leftIdx] = highLeftVal
    if cell[leftIdx] > highLeftVal: highLeftVal = cell[leftIdx]

    lowRight[rightIdx] = lowRightVal
    if cell[rightIdx] < lowRightVal: lowRightVal = cell[rightIdx]

然后，检查每个单元格（第一个和最后一个单元格）的简单问题就是确保该值既大于左侧最高，又小于右侧的最低值（根据您的问题，此答案假设“较高/较低”是字面意思，而不是“大于/小于或等于”）：

for each idx 1 thru cell.lastIndex-1 inclusive:
    if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]
        print "Found value ", cell[idx], " at index ", idx

您可以在下面看到初始通过的结果：

highLeft:   -  1  3  3  6  6  7  9  9 10 10
cells   :   1  3  2  6  5  7  9  8 10  8 11
lowRight:   2  2  5  5  7  8  8  8  8 11  -
                           ^

值相对于其上方和下方的两个值进行排序（非非非包含性）的唯一候选单元格是标记为 。7^

现在请记住，这是一个相对易于理解的解决方案，可以找到满足约束的多个项目。鉴于您只需要一个项目，则可以获得更好的性能（尽管它仍然是O（n））。

基本思想是从左到右遍历数组，对于每个单元格，检查左侧的所有内容是否较低，右侧的所有内容是否较高。

第一点很容易，因为通过从左到右遍历，您可以记住遇到的最高值。第二点似乎涉及以某种方式展望未来，但有一个技巧可以用来避免这种“时间体操”。

这个想法是保持当前单元格左侧看到的最大值和当前答案的索引（最初设置为哨兵值）。

如果当前答案是哨兵值，则选择满足“大于左侧所有内容”的第一个单元格作为可能的答案。

而且，只要情况仍然如此，这就是您选择的细胞。但是，一旦您在其右侧找到一个小于或等于它的位置，它就不再有效，因此您将丢弃它并再次开始搜索。

此搜索从当前点开始，而不是从一开始就发生，因为：

• 当前答案之后的所有内容，但排除此（小于或等于）单元格都高于当前应答器，否则您已经找到了一个较小或相等的单元格;和
• 因此，此单元格必须小于或等于该范围中的每个单元格，因为它小于或等于当前答案;因此
• 该范围内没有单元格有效，它们都大于或等于此单元格。

处理完非最终项目后，您的答案将是哨兵或几乎满足约束的单元。

我之所以说“几乎”，是因为需要进行最后一次检查，以确保最终项目大于它，因为您在遍历过程中没有对该项目执行任何检查。

因此，该野兽的伪代码是这样的：

# Store max on left and start with sentinel.

maxToLeft = cell[0]
answer = -1

for checking = 1 to cell.lastIndex-1 inclusive:
    switch on answer:
        # Save if currently sentinel and item valid.
        case -1:
            if cell[checking] > maxToLeft:
                answer = checking

        # Set back to sentinel if saved answer is now invalid.
        otherwise:
            if cell[answer] >= cell[checking]:
                answer = -1

    # Ensure we have updated max on left.

    if cell[checking] > maxToLeft:
        maxToLeft = cell[checking]

# Final check against last cell.

if answer != -1:
    if cell[cell.lastIndex] <= cell[answer]:
        answer = -1

由于我的伪代码（主要）基于Python，因此提供更具体的代码示例是一件相当简单的事情。首先，“找到所有可能性”选项：

cell = [1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]

highLeft = [0] * len(cell)
lowRight = [0] * len(cell)

highLeftVal = cell[0]
lowRightVal = cell[len(cell)-1]

rightIdx = len(cell) - 1
for leftIdx in range(1, len(cell)):
    rightIdx = rightIdx - 1

    highLeft[leftIdx] = highLeftVal
    if cell[leftIdx] > highLeftVal: highLeftVal = cell[leftIdx]

    lowRight[rightIdx] = lowRightVal
    if cell[rightIdx] < lowRightVal: lowRightVal = cell[rightIdx]

print(highLeft)
print(cell)
print(lowRight)

for idx in range(1, len(cell) - 1):
    if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]:
        print("Found value", cell[idx], "at index", idx)

第二个，稍微更有效的选项，但只能找到一种可能性：

cell = [1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
maxToLeft = cell[0]
answer = -1
for checking in range(1, len(cell) - 1):
    if answer == -1:
        if cell[checking] > maxToLeft:
            answer = checking
    else:
        if cell[answer] >=cell[checking]:
            answer = -1
    if cell[checking] > maxToLeft:
        maxToLeft = cell[checking]

if answer != -1:
    if cell[len(cell] - 1] <= cell[answer]:
        answer = -1

if answer == -1:
    print ("Not found")
else:
    print("Found value", cell[answer], "at index", answer);


print(highLeft)
print(cell)
print(lowRight)

for idx in range(1, len(cell) - 1):
    if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]:
        print("Found value", cell[idx], "at index", idx)

这两个代码的输出（尽管后一个示例仅显示最后一行）基本上显示了伪代码的用途：

[0, 1, 3, 3, 6, 6, 7, 9, 9, 10, 10]
[1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
[2, 2, 5, 5, 7, 8, 8, 8, 8, 11, 0]
Found value 7 at index 5