我看過一些關于下一個更大元素的帖子。我正在為其變體之一尋找性能更高的解決方案。
問題：我有一個數字陣列。我想知道每個數字的下一個索引值變得大于 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) 演算法可以解決這個問題。但這對我的需求來說太慢了。
有誰知道一個更快的演算法來解決這個問題或其接近的變體之一？
uj5u.com熱心網友回復：
我會使用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]
uj5u.com熱心網友回復：
您可以在陣列中創建索引和值的元組串列。按值對串列進行排序。然后，您可以使用兩個指標遍歷串列，找到大于給定百分比的值并捕獲相應的索引。復雜度為 O(nlogn)
java 17 中的示例實作如下：
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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422803.html
標籤：