在Matlab中找到反转次数

Question

在通过分而治之的方法查找数组中的反转次数的过程中我遇到了实现merge-step的问题:我们有两个排序的数组,任务是计算第一个数组的元素时的个案数大于第二个元素.

例如,如果是数组v1 = [1,2,4], v2 = [0,3,5],我们应该计算4次反转.

所以,我在Matlab中实现了合并步骤,但我坚持如何快速实现它的问题.

首先,我尝试过蛮力方法

tempArray = arrayfun(@(x) length(find(v2>x)), v1)

它的工作速度和下一个片段一样慢

l = 1;
s = 0;
for ii = 1:n1 
    while(l <= n2 && p1(ii)>p2(l))
        l = l + 1;
    end
    s = s + l - 1;
end

有没有一种方法可以让它更快？

编辑

谢谢你的答案和方法!我为进一步的工作找到了有趣的东西.

这是片段,它应该是我尝试过的最快的片段

n1 = length(vec1); n2 = length(vec2);

uniteOne = [vec1, vec2];

[~, d1] = sort(uniteOne);
[~, d2] = sort(d1); % Find ind-s IX such that B(IX) = A, where B = sort(A)
vec1Slice = d2(1:n1);
finalVecToSolve = vec1Slice - (1:n1);

sum(finalVecToSolve)

Answer 1

另一种蛮力方法bsxfun-

sum(reshape(bsxfun(@gt,v1(:),v2(:).'),[],1))

或者,正如@thewaywewalk在评论中提到的,用于nnz替换summing-

nnz(bsxfun(@gt,v1(:),v2(:).'))