数组中每个元素一定百分比的下一个更大的元素

Question

我看过一些关于下一个更大元素的帖子。我正在为其变体之一寻找性能更高的解决方案。

问题：我有一组数字。我想知道每个数字的下一个索引值大于 X 的百分比。

示例：假设我有这个数组 [1000, 900, 1005, 1022, 1006] 并且我将目标设置为 1%。同时，我想知道这个值什么时候比原来大1%。

1000 -> We want to know when value become bigger of equal to 1010    -> Index = 3
 900 -> We want to know when value become bigger of equal to  909    -> Index = 2
1005 -> We want to know when value become bigger of equal to 1015.05 -> Index = 3
1022 -> We want to know when value become bigger of equal to 1030.2  -> Index = -1
1006 -> We want to know when value become bigger of equal to 1016.06 -> Index = -1

天真的解决方案： O(n^2) 算法可以解决该问题。但它对我的需求来说太慢了。

有谁知道解决此问题的更快算法或其近似变体之一？

Answer 1

我会使用 min heap。最小堆中的每个元素都是一个元组 (value, index)，其中 value 是目标值，index 是输入数组中目标值的索引。

那么算法就是：

create an output array with all elements set to -1
for each element in the input array
   for each target value on the min heap less than the element's value
      pop the (targetValue, targetIndex) tuple
      record the index of the current input element at the target index
   add the current element (value, index) tuple to the min heap

例如，给定问题中的数组，算法执行以下步骤：

创建一个所有元素都设置为 -1 的输出数组
读取1000，将(1010, 0)放入最小堆
读取900，将(909, 1)放入最小堆
读取 1005。它大于 909，因此弹出 (909, 1)，并记录索引 2 作为元素 909 的答案。将 (1015.05, 2) 放入最小堆。
读取1022。从最小堆中弹出(1010, 0)然后(1015.05, 2)，记录索引3作为元素1000和1005的答案。将(1030.2, 3)放入最小堆中。
读取1006，将(1016.06, 4)放入最小堆
由于已经到达输入数组的末尾，(1030.2, 3)和(1016.06, 4)永远不会出栈，输出数组中对应的元素保持为-1

运行时间为O(nlogn).

示例 python 实施：

from heapq import heappush, heappop

def nextGreater(inputArray):
    targetHeap = []
    outputArray = [-1] * len(inputArray)
    for inputIndex, inputValue in enumerate(inputArray):
        while targetHeap and targetHeap[0][0] < inputValue:
            targetValue, targetIndex = heappop(targetHeap)
            outputArray[targetIndex] = inputIndex
        heappush(targetHeap, (inputValue * 1.01, inputIndex))
    return outputArray

inputArray = [1000, 900, 1005, 1022, 1006]
outputArray = nextGreater(inputArray)
print outputArray  # [3, 2, 3, -1, -1]

Answer 2

您可以在数组中创建索引和值的元组列表。按值对列表进行排序。然后，您可以使用两个指针查找大于给定百分比的值并捕获相应的索引来遍历列表。复杂度为 O(nlogn)

java17 中的实施示例如下：

final double percentage = 1.01;

int[] arr = new int[]{1000, 900, 1005, 1022, 1006};

record KeyValuePair(int value, int index) {}

List<KeyValuePair> keyValuePairs = new ArrayList<>();
for (int i = 0; i < arr.length; ++i) {
    keyValuePairs.add(new KeyValuePair(arr[i], i));
}

keyValuePairs.sort(Comparator.comparingInt(KeyValuePair::value));

int i = 0, j = 1;
while (i != keyValuePairs.size() && j != keyValuePairs.size()) {
    if (keyValuePairs.get(i).value() * percentage < keyValuePairs.get(j).value()) {
        if (keyValuePairs.get(i).index() < keyValuePairs.get(j).index()) {
            System.out.println("For index " + keyValuePairs.get(i).index() + " -> " + keyValuePairs.get(j).index());
        } else if (keyValuePairs.get(i).index() + 1 != keyValuePairs.size()) {
            System.out.println("For index " + keyValuePairs.get(i).index() + " -> " + (keyValuePairs.get(i).index() + 1));
        }
        ++i;
    } else {
        ++j;
    }
}

数组中每个元素一定百分比的下一个更大的元素

Next greater element over a certain percentage of each element in array

arrays

algorithm

stack

dynamic-programming

data-structures