2

如果我有 20 对坐标，其 x 和 y 值是：

x   y
27  182
180 81
154 52
183 24
124 168
146 11
16  90
184 153
138 133
122 79
192 183
39  25
194 63
129 107
115 161
33  14
47  65
65  2
1   124
93  79

现在，如果我随机生成 15 对坐标 (x,y) 并想与上面给出的这 20 对坐标进行比较，如何在没有嵌套循环的情况下最有效地做到这一点？

4

3 回答 3

3

如果您想查看 15 个随机生成的坐标对中的任何一个是否等于 20 个原始坐标对中的任何一个，一个简单的解决方案是使用ISMEMBER函数，如下所示：

oldPts = [...];  %# A 20-by-2 matrix with x values in column 1
                 %#   and y values in column 2
newPts = randi(200,[15 2]);  %# Create a 15-by-2 matrix of random
                             %#   values from 1 to 200
isRepeated = ismember(newPts,oldPts,'rows');

并且isRepeated将是一个 15×1 逻辑数组，其中newPts存在一行，oldPts否则为零。

于 2011-05-03T19:19:52.033 回答
1

如果您的坐标是 1）实际上是整数和 2）它们的跨度是合理的（否则使用稀疏矩阵），我将使用一个简单的真值表。像

x_0= [27 180 ...
y_0= [182 81 ...
s= [200 200]; %# span of coordinates
T= false(s);
T(sub2ind(s, x_0, y_0))= true;
%# now obtain some other coordinates
x_1= [...
y_1= [...
%# and common coordinates of (x_0, y_0) and (x_1, y_1) are just
T(sub2ind(s, x_1, y_1))
于 2011-05-04T13:13:50.010 回答
0

如果你原来的二十个点不会改变，那么如果你对它们进行排序 O(n log n); 你会得到更好的效率；然后您可以通过 O(log n) 搜索查看每个随机点是否在列表中。

如果您的“原始”点列表更改（插入/删除），您可以获得与二叉树相同的性能。

但是：如果您正在使用的点数真的和您的问题一样低，那么您的双循环可能只是最快的方法！随着数据量变得非常大，具有低 Big-O 曲线的算法会更快，但它通常以一次性减速为代价（在你的情况下，排序） - 并且只有 15x20 个数据点......那里不会是人类可感知的差异；如果您在系统时钟上计时，您可能会看到一个。或者你可能不会。

希望这可以帮助！

于 2011-05-03T18:52:00.900 回答