如何高效生成不重复的随机坐标点
在 php 中，生成不重复的随机坐标点对于需要在空间内分布对象的应用程序非常重要。面试中经常会遇到这个问题，例如在 100*100 的矩阵中生成 200 个不重复的坐标点。
以下提供了几种实现此功能的方法：
1. 随机生成并去重
立即学习“PHP免费学习笔记（深入）”；
此策略涉及生成随机坐标点，然后遍历它们并删除所有重复出现的值。虽然简单易懂，但它在处理大量坐标点时效率低下。
2. 生成所有坐标点
另一种方法是生成所有可能的坐标点，然后从中随机选择 200 个。虽然确保了所有坐标点都是不重复的，但生成所有坐标点的步骤效率很低，尤其是在网格很大的情况下。
3. 使用 hash 表
可以使用 hash 表（也称为哈希映射）更有效地解决此问题。hash 表是一种数据结构，它将键映射到值，查找或插入操作时间复杂度为 o(1)。
下面是一个高效的 php 代码示例，使用 hash 表生成 200 个不重复的坐标点：
function generateCoordinates($width, $height, $numPoints) {
$coordinates = array();
$map = array();
for ($i = 0; $i < $numPoints; $i++) {
$x = rand(0, $width - 1);
$y = rand(0, $height - 1);
$key = "$x:$y";
if (!isset($map[$key])) {
$coordinates[] = [$x, $y];
$map[$key] = true;
}
}
return $coordinates;
}此方法的时间复杂度为 o(n)，其中 n 是生成坐标点的数量。它通过使用 hash 表来避免重复，而不是遍历所有生成的坐标点或生成所有可能的坐标点。
