在列表中查找比当前元素大 n 倍的第一个元素

Question

很容易想出一个O(n)算法来解决这个非常著名的问题：

对于列表中的每个元素，找到比它大的第一个元素。这可以使用堆栈来完成。但是，如果我想找到大于 n*current 元素的第一个元素怎么办？

进一步来说：

给定一个数组 [2, 5, 4, 7, 3, 8, 9, 6] 并且 n = 2。

我想要 [5, -1, 9, -1, 8, -1, -1, -1] 对于 2, 5 是下一个大于 n * 2 的元素，对于 4, 9 是下一个大于 n * 的元素4. 对于 5，没有大于 n * 5 的元素，因此在该位置返回 -1。

我们能做得更好O(n^2)吗？

Answer 1

我同意 OP 的观点，在剩余数组中查找第一个元素 > 2x 时，O(N) 算法的简单谓词可能不适用于基于堆栈的解决方案。

顺便说一句，我找到了一个 O(NlogN) 解决方案。

它使用最小堆来维护我们感兴趣的前沿元素。

伪代码：

def get_2x_elements(input_list, multipler = 2):
  H = [] #min-heap with node-values as tuples (index, value)
  R = [-1 for _ in range(len(input_list))] # results-list

  for index, value in enumerate(input_list):
    while multiplier*H[0][1] < value:
      minval = extractMinFromHeap(H)
      R[minval[0]] = value

  insertToMinHeap(H, (index, value))

  return R

复杂性分析：

1. Insertion/Extraction from min-heap = O(logN)
2. Number of such operations = N

Total-complexity = O(NlogN)

PS：这假设我们需要first >2x element列表的其余部分。

回复：我对你的想法做了一个 Java 版本的实现。谢谢@Serial Lazer

def get_2x_elements(input_list, multipler = 2):
  H = [] #min-heap with node-values as tuples (index, value)
  R = [-1 for _ in range(len(input_list))] # results-list

  for index, value in enumerate(input_list):
    while multiplier*H[0][1] < value:
      minval = extractMinFromHeap(H)
      R[minval[0]] = value

  insertToMinHeap(H, (index, value))

  return R