This question already has an answer here:
这个问题已经有了答案:
- Greatest element present on the right side of every element in an array 3 answers
- 数组3中每个元素的右边都有一个最大的元素
Given an array , for every element I need to find the smallest element to the right of the given element which is greater than the current element.
给定一个数组，对于每个元素，我都需要找到位于给定元素右边的最小元素，该元素大于当前元素。
Mathematically, For every index i in array A, I need to find index j such that
数学上，对于数组A中的每一个索引i，我都需要找到这样的索引j
A[j] > A[i]
j > i
A[j] - A[i] is minimum
I need to find j for every index i
我需要为每个索引I找到j
The brute force solution would be O(n^2) and I am hoping to do better. I am thinking that an O(n log n) solution is possible using self-balancing BST but that seems pretty complex. Moreover I need a O(n) solution.
蛮力解决方案是O(n ^ 2),我希望能做得更好。我认为使用自平衡BST可以得到O(n log n)解，但这看起来相当复杂。而且我需要O(n)解。
Is there a O(n) solution to this problem? Is there a proof that the lower bound is O(n log n)?
这个问题有O(n)解吗?有证据证明下界是O(n log n)吗?
1 个解决方案
#1
9
Proof of O(nlogn) lower bound: (for comparison based algorithms)
O(nlogn)下界证明(基于比较的算法)
Lets say we have a comparison-based algorithm that would accomplish this task in O(n). That is for each index, we have the immediate greater element to its right (say R[i]).
假设我们有一个基于比较的算法，可以在O(n)中完成这个任务。也就是说，对于每个索引，右边都有一个较大的元素(R[i])。
Similarly we can run this algorithm on the reversed input array and then reverse the result. For each index we have the immediate greater element to its left (say L[i]).
类似地，我们可以在反向输入数组上运行该算法，然后反转结果。对于每个索引，我们在其左边有直接较大的元素(比如L[i])。
This means that in O(n) we have for each element, the immediate greater element in the array = min (R[i], L[i]).
这意味着在O(n)中，对于每个元素，数组中的直接较大元素= min (R[i]， L[i])。
We can now sort the array using this information.
现在我们可以使用这些信息对数组进行排序。
Find the minimum element in the array. Find its successor (immediate greater element), then its successor's successor etc. Hence you would have got the entire array in sorted order.
找到数组中的最小元素。找到它的继承者(直接的大元素)，然后是它的继承者等等。这样你就能把整个数组按顺序排列。
Sorted the array in O(n) using only comparisons (a contradiction).
用O(n)排序数组，只使用比较(矛盾)。
O(nlogn) Algorithm:
Start building the balanced BST from the right of the array. The nodes would contain the values and the respective indices.
O(nlogn)算法:从数组的右边开始构建平衡的BST。节点将包含值和各自的索引。
Then for each new element encountered, inserting it in the BST would get corresponding nearest larger index/value.
然后，对于所遇到的每个新元素，将其插入到BST中，将得到相应的更大的索引/值。
#1
9
Proof of O(nlogn) lower bound: (for comparison based algorithms)
O(nlogn)下界证明(基于比较的算法)
Lets say we have a comparison-based algorithm that would accomplish this task in O(n). That is for each index, we have the immediate greater element to its right (say R[i]).
假设我们有一个基于比较的算法，可以在O(n)中完成这个任务。也就是说，对于每个索引，右边都有一个较大的元素(R[i])。
Similarly we can run this algorithm on the reversed input array and then reverse the result. For each index we have the immediate greater element to its left (say L[i]).
类似地，我们可以在反向输入数组上运行该算法，然后反转结果。对于每个索引，我们在其左边有直接较大的元素(比如L[i])。
This means that in O(n) we have for each element, the immediate greater element in the array = min (R[i], L[i]).
这意味着在O(n)中，对于每个元素，数组中的直接较大元素= min (R[i]， L[i])。
We can now sort the array using this information.
现在我们可以使用这些信息对数组进行排序。
Find the minimum element in the array. Find its successor (immediate greater element), then its successor's successor etc. Hence you would have got the entire array in sorted order.
找到数组中的最小元素。找到它的继承者(直接的大元素)，然后是它的继承者等等。这样你就能把整个数组按顺序排列。
Sorted the array in O(n) using only comparisons (a contradiction).
用O(n)排序数组，只使用比较(矛盾)。
O(nlogn) Algorithm:
Start building the balanced BST from the right of the array. The nodes would contain the values and the respective indices.
O(nlogn)算法:从数组的右边开始构建平衡的BST。节点将包含值和各自的索引。
Then for each new element encountered, inserting it in the BST would get corresponding nearest larger index/value.
然后，对于所遇到的每个新元素，将其插入到BST中，将得到相应的更大的索引/值。