这是我在一家科技公司遇到的面试问题。我弄错了,我认为这注定了我的机会,但老实说,我仍然无法弄清楚答案……这是问题所在。假定该序列的所有元素都是唯一的。
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 并维护到目前为止看到的元素的顺序统计树。参见 en.wikipedia/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 en.wikipedia/wiki/Order_statistic_tree
更多推荐
给定两个数组,找到更多的元素
发布评论