我用英语问了这个问题
Given two arrays, find the number of elements greater
然后我意识到我说的完全错了,所以我再问一遍。
我们有两个有限序列:X={Xi},Y={Yi},其中Yi是Xi的一个子序列。
让我们把它们写成单独的数组:[X1,X2,…,Xn],[Y1,Y2,…,Yk]其中n是X的长度,k是Y的长度,显然,因为Y是X的子序列,所以我们有n>=K
例如
X=[1, 10, 5, 7, 11, -4, 9, 5]
y=[10, 7, -4, 9]
然后,对于Y中的每个元素,我们想找到X中第一个元素,1)出现在该元素之后,2)大于该元素。如果没有这样的元素,我们只使用-1
使用上面的例子
X=[1, 10, 5, 7, 11, -4, 9, 5]
y=[10, 7, -4, 9]
ans=[11, 11, 9, -1]
说明:
ans的第一个元素是11,因为只有11是在X中出现在10之后且大于10的第一个数字
ans的第二个元素也是11,因为11是X中7之后出现的第一个数字。
ans的第三个元素也是9,因为9是出现在-4之后的第一个数字,并且都大于-4
第四个元素是-1,因为X中没有大于9的元素出现在后面。
问题是在O(N)时间复杂度下解决它,其中N是X的长度。有人有想法吗?
