arrays - 在 Matlab 中查找反转次数

Question

在通过分而治之的方法查找数组中的反转次数的过程中，我遇到了实现合并步骤的问题:我们有两个排序数组，任务是计算元素为第一个数组大于第二个数组中的元素。

例如，如果数组是 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(:).'))