2

我有一个大小为 3XN 的矩阵。矩阵中的每一列都是一个 3d 点。我想删除重复项，我只关心前 2 个维度中的重复项。如果存在重复点（即 x,y 相同），我想选择第三维（z 坐标）中值最高的点。例如：（前 2 个维度是前 2 行）

M = [ 1 1 1 2 3 4 5 5 ;
      4 4 4 6 6 3 2 2 ;
      3 4 5 3 4 5 7 8 ];
          ^ ^ ^ ^   ^

我想得到：

Res = [ 1 2 3 4 5 ;
       4 6 6 3 2 ;
       5 3 4 5 8]

我需要它尽可能快地工作，因为矩阵非常大。所以，如果可能的话，不用排序。我正在寻找一个matlab“快捷方式”来做到这一点，而不需要循环或排序。谢谢matlabit

4

2 回答 2

3

这可以通过以下方式轻松有效地完成accumarray：

% - choose pairs of row/column indices - first two rows of M
% - accumulate using MAX of the values in the third row - this step removes the duplicates
res = accumarray(M(1:2,:)', M(3,:)', [], @max);

% i/j indices of non-zero entries in the result matrix are
% the unique index pairs, and the value is the maximum third row
% value for all duplicates
[i, j, v] = find(res);

% construct the result matrix
[i j v]'


ans =

 5     4     1     2     3
 2     3     4     6     6
 8     5     5     3     4

如果您的索引非常大并且res由于内存原因无法创建矩阵，则可以使用accumarray函数的稀疏版本 - 它创建一个稀疏矩阵，它只存储非零条目。其余的保持不变：

res = accumarray(M(1:2,:)', M(3,:)', [], @max, 0, true);
于 2012-12-05T09:34:47.763 回答
0

扫描前 2 行并将元素插入到max-heap. 插入时，您可以即时检查元素是否已存在（在这种情况下不要将其插入堆中）。如果存在，将其与当前最大值进行比较，并在需要时设置为最大值。最终的最大值是您寻求的结果。

构建堆的复杂性是O(n)并且检查最大值不会超出此边界。因此，与使用排序O(n)的 if 相比，总时间复杂度为。O(nlogn)还需要额外的O(n)空间。

于 2012-12-05T07:17:51.667 回答