给定两个数组，找到更多的元素 [英] Given two arrays, find the number of elements greater

问题描述

这是我在一家科技公司遇到的面试问题。我弄错了，我认为这注定了我的机会，但老实说，我仍然无法弄清楚答案……这是问题所在。假定该序列的所有元素都是唯一的。

This was the interview question I had from a tech company. I got it wrong, which I think doomed my chances, but I honestly I still cannot figure out the answer... here's the question. Assume that all elements of the sequence are unique.

我们有两个有限序列：X = {Xi}，Y = {Yi}其中Yi是的子序列兮。

We have two finite sequences: X={Xi}, Y={Yi} where Yi is a sub-sequence of Xi.

让我们将它们写为单独的数组：[X1，X2，...，Xn]，[Y1，Y2，...，Yk]其中n是长度在X中，k是Y的长度，显然，由于Y是X的子序列，因此n> = k。

Let's write them as separate arrays: [X1, X2, ..., Xn], [Y1, Y2, ..., Yk] where n is the length of X, k is the length of Y, and obviously, since Y is a sub-sequence of X, we have n>=k.

例如

X=[1, 10, 5, 7, 11, -4, 9, 5]
y=[10, 7, -4, 9]

然后，对于Y中的每个元素，我们要查找X中 1）出现在该元素之后的元素数量，并且 2）大于该元素 。

Then for each element in Y, we want to find the number of elements in X which 1) appear after that element and 2) greater than that element.

使用上面的示例

X=[1, 10, 5, 7, 11, -4, 9, 5]
y=[10, 7, -4, 9]
ans=[1, 2, 2, 0]

explanation:

the first element of ans is 1 because only 11 appears after 10 and greater than 10 in X, 
so there's only 1 element

second element of ans is 2 since 11, 9 both appear after 7 in X, so there are 2 elements 
that appear after 7 and greater than 7. 

the third element of ans is also 2 since 9, 5 appear after -4 and are both greater than 
-4 in X. 

the fourth element is 0 since no element in X appears after and greater than 9.

面试官要我解决O（N）时间复杂度，其中N是X的长度。我没有找到方法。

The interviewer wanted me to solve it in O(N) time complexity where N is the length of X. I did not find how.

有人有想法吗？

推荐答案

如果有一种算法可以可以解决此问题，然后通过设置 Y = X ，可以使其提供足够的信息来对 X 进行排序 X 中元素之间的进一步比较。因此，在通常的假设下，您不能在线性时间内执行此操作，即 X 中的任意整数可以在恒定时间内进行操作，但没有常数限制

If have an algorithm that can solve this problem, then by setting Y = X, you can make it provide enough information to sort X without any further comparisons among elements in X. Therefore, you can't do this in linear time under the usual assumptions, i.e., arbitrary integers in X that you can do operations on in constant time, but no constant bound on their size.

您可以在O（N log N）时间内轻松完成操作，只需向后走过 X 并维护到目前为止看到的元素的顺序统计树。参见 https://en.wikipedia.org/wiki/Order_statistic_tree

You can do it in O(N log N) time pretty easily by walking backwards through X and maintaining an order statistic tree of the elements seen so far. See https://en.wikipedia.org/wiki/Order_statistic_tree

这篇关于给定两个数组，找到更多的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！