获取数组前缀中的主导元素
Get dominating elements in the prefix of an array
给定一个大小为 N 的数组 A，对于每个元素 A[i]，我想找到所有 j 使得 A[j] > A[i]。目前，我想不出比 O(i)（遍历所有 0 <= j < i 并检查）更好的方法。是否有一种算法可以实现比上述更好的时间复杂度？ Space 复杂度可以是 O(N)
更新 1
我们可以假设数组具有不同的元素
更新 2
让我们考虑数组 A = [4 6 7 1 2 3 5]。让 dom(i) = {j | 0 < j < i 使得 A[j] > A[i] }
- dom(0) = 空
- dom(1) = 空
- dom(2) = 空
- dom(3) = {0, 1, 2}
- dom(4) = {0, 1, 2}
- dom(5) = {0, 1, 2}
- dom(6) = {1, 2}
此外，O(N) 的 space 复杂度意味着每次迭代 i
无法实现更低的时间复杂度，例如，如果您的数组全部递减，则所有列表的总长度将是二次方的，因此如果您的任务是获取列表，这是尽可能快的.您的解决方案已经实现了这个 O(N^2)，因此它已经是最优的。
不过，有一些更快的方法可以计算与此相关的一些事情。例如，如果您实际上只想获得所有此类对的总数，则可以在 O(n ln n) 时间内完成，请参阅 this post.
给定一个大小为 N 的数组 A，对于每个元素 A[i]，我想找到所有 j 使得 A[j] > A[i]。目前，我想不出比 O(i)（遍历所有 0 <= j < i 并检查）更好的方法。是否有一种算法可以实现比上述更好的时间复杂度？ Space 复杂度可以是 O(N)
更新 1
我们可以假设数组具有不同的元素
更新 2
让我们考虑数组 A = [4 6 7 1 2 3 5]。让 dom(i) = {j | 0 < j < i 使得 A[j] > A[i] }
- dom(0) = 空
- dom(1) = 空
- dom(2) = 空
- dom(3) = {0, 1, 2}
- dom(4) = {0, 1, 2}
- dom(5) = {0, 1, 2}
- dom(6) = {1, 2}
此外，O(N) 的 space 复杂度意味着每次迭代 i
无法实现更低的时间复杂度，例如，如果您的数组全部递减，则所有列表的总长度将是二次方的，因此如果您的任务是获取列表，这是尽可能快的.您的解决方案已经实现了这个 O(N^2)，因此它已经是最优的。
不过，有一些更快的方法可以计算与此相关的一些事情。例如，如果您实际上只想获得所有此类对的总数，则可以在 O(n ln n) 时间内完成，请参阅 this post.