在列表中找到比当前元素大 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所以return -1位置。

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

Answer 1

当然，很容易。

我们只需要一个排序版本的数组（排序后的元素加上它们的原始索引），然后我们就可以进行有效的搜索（修改后的二分搜索），将我们指向大于元素的开始当前数字（或者它的倍数，没关系）。然后我们可以按顺序搜索那些具有最小索引的元素（如果需要，它大于当前数字之一）。

编辑：有人指出算法不一定比O(n²)好，因为顺序搜索满足大于条件的元素。可能是这样，我不确定。但请注意，我们可能会构建一个更复杂的搜索结构，以某种方式已经涉及索引。这是留作作业。 :)

Answer 2

我同意 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：假设我们需要列表剩余部分的 first >2x element。

回复：我对你的想法进行了 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;
    }

Answer 3

基于堆栈的解决方案 offered at geeksforgeeks 似乎没有保持结果中元素的顺序，即使在其输出中也是如此：

input: int arr[] = { 11, 13, 21, 3 };
output: 
 11 -- 13
 13 -- 21
 3 -- -1
 21 -- -1

在找到比电流大 N 倍的第一个元素后，该算法在给定示例中无法检测到元素 4 的 9。

Online demo

input: int arr[] = { 2, 5, 4, 7, 3, 8, 9, 6 }; // as in this question
output: 
2 * 2 --> 5
2 * 3 --> 8
6 -- -1
9 -- -1
8 -- -1
7 -- -1
4 -- -1
5 -- -1

因此，关于复杂度为 O(N) 的现有解决方案的初始假设并不完全适用于预期结果。

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

Find the first element that is n times larger than current element in a list

algorithm

computer-science

list

伪代码：

复杂性分析：