2

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

例如，如果数组是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)
4

3 回答 3

6

另一种蛮力方法bsxfun-

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

或者，正如@thewaywewalk 在评论中提到的那样，使用nnz替换summing-

nnz(bsxfun(@gt,v1(:),v2(:).'))
于 2015-09-24T17:08:29.773 回答
4

代码

n = numel(v1);
[~, ind_sort] = sort([v1 v2]);
ind_v = ind_sort<=n;
result = sum(find(ind_v))-n*(n+1)/2;

解释

n表示输入向量的长度。ind_v是一个长度向量2*n，表示 的值v1并v2排序在一起，其中1表示从 的值v1，0表示从 的值v2。对于你的例子，

v1 = [1,2,4];
v2 = [0,3,5];

我们有

ind_v =
     0     1     1     0     1     0

的第一项ind_v是零。v1这意味着和中的最小值v2（即0）属于v2。然后有一个，因为第二低的值（即1）属于v1。的最后一项为零ind_v，因为输入向量的最大值（即）属于。5v2

由此ind_v很容易计算结果。也就是说，我们只需要计算每个 0 的左边有多少个零，然后将所有这些计数相加。

我们甚至不需要进行计数；我们可以从每一个的位置推断出它们。第一个左边的零的数量是那个减号的位置。第二个左边的零的数量是它的位置减。等等。因此会给出预期的结果。但是，所以结果可以简化为。12sum(find(ind_v)-(1:n))sum(1:n)n*(n+1)/2sum(find(ind_v))-n*(n+1)/2

复杂

对向量进行排序是这里的限制操作，并且需要O(2*n*log(2*n))算术比较。相反，蛮力需要O(n^2)比较。

于 2015-09-24T22:45:15.083 回答
3

一种明确的方法可能是减去您的元素并查看它们的负数：

v1 = [1,2,4];
v2 = [0,3,5];

mydiffs = zeros(length(v1), length(v2));
for ii = 1:length(v1)
    mydiffs(ii,:) = v2 - v1(ii);
end

test = sum(reshape(mydiffs,[],length(v1)*length(v2)) < 0)

返回：

test =

     4

这不是最漂亮的方法，肯定有改进的余地。我也怀疑它比bsxfun方法更快。

Edit1：一种arrayfun看起来更整洁但不一定比循环更快的方法。

test = arrayfun(@(x) (v2 - x) < 0, v1, 'UniformOutput', false);
inversions = sum([test{:}]);

Edit2：一种repmat方法

inversions = nnz(repmat(v2, length(v2), 1) - repmat(v1', 1, length(v1)) < 0)
于 2015-09-24T17:14:04.720 回答