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

Question

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

For every element in the list, find the first element that is larger than it. This can be done using a stack. But, what if I want to find the first element that is larger than n*current element?

更具体地说:

给定一个数组 [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) 的解决方案。

它使用Min-heap来维护我们感兴趣的前沿元素。

伪代码:

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:假设我们需要列表剩余部分的第一个 >2x 元素。

回复:我为你的想法做了一个 Java verion 实现。谢谢@Serial Lazer

    private static class ValueAndIndexPair implements Comparable<ValueAndIndexPair>{
        public final double value;
        public final int index;

        public ValueAndIndexPair(double value, int index) {
            this.value = value;
            this.index = index;
        }

        @Override
        public int compareTo(ValueAndIndexPair other) {
            return Double.compare(value, other.value);
        }
    }

    public static double[] returnNextNTimeLargerElementIndex(final List<Double> valueList, double multiplier) {
        double[] result = new double[valueList.size()];
        PriorityQueue<ValueAndIndexPair> minHeap = new PriorityQueue<>();

        // Initialize O(n)
        for (int i = 0; i < valueList.size(); i++) {
            result[i] = -1.0;
        }
        if (valueList.size() <= 1) return result;

        minHeap.add(new ValueAndIndexPair(valueList.get(0) * multiplier, 0));

        for (int i = 1; i <valueList.size(); i++) {
            double currentElement = valueList.get(i);
            while (!minHeap.isEmpty() && minHeap.peek().value < currentElement) {
                result[minHeap.poll().index] = currentElement;
            }
            minHeap.add(new ValueAndIndexPair(currentElement * multiplier, i));
        }
        return result;
    }