在通过分而治之的方法查找数组中的反转次数的过程中,我遇到了实现合并步骤的问题:我们有两个排序数组,任务是计算元素为第一个数组大于第二个数组中的元素。
例如,如果数组是 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)
最佳答案
另一种蛮力方法 bsxfun
-
sum(reshape(bsxfun(@gt,v1(:),v2(:).'),[],1))
或者,正如@thewaywewalk 在评论中提到的那样,使用 nnz
来替换 summing
-
nnz(bsxfun(@gt,v1(:),v2(:).'))
关于arrays - 在 Matlab 中查找反转次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32767105/