在排除一组位置的n * n矩阵中选择随机位置的最优雅/最有效的方法是什么？
示例：想象一个棋盘，所以n = 8，总共有8 * 8 = 64个位置。（0，0），（5，3），（7，4）位置有3个棋子。任务是选择一个尚未被棋子占据的随机位置。
这是我想出的：
def get_random_position(n, occupied_positions):
while True:
random_position = (random.choice(range(n)), random.choice(range(n)))
if random_position not in occupied_positions:
return random_position
if __name__ == '__main__':
unoccupied_random_position = get_random_position(8, [(0, 0), (5, 3), (7, 4)])
print(unoccupied_random_position)
时间复杂度对于n是恒定的，并且与所占用的单元数成线性关系。因此，如果90％的单元已被占用，则循环将迭代更长的时间。
有更好的方法吗？
首先，很明显，您不能做得比O（m）的最坏情况还要好，其中m是矩阵中的像元数，即m =n²，其中n是矩阵的宽度：在最坏的情况下，所有除了一个单元格以外的其他单元格，您至少需要查看这些m-1坐标中的每个坐标。
我还要在这里提到的是，在您的代码random_position not in occupied_positions中不是一个常量操作。每次迭代该列表以查找匹配项。
这是一个替代方案：
您可以导出空闲单元的数量，生成一个达到该限制的随机数，然后迭代占用的单元以使该数字（递增）适应实际的空闲单元。在此过程中，数字唯一地映射到x和y坐标。
为使此方法有效，我们必须假定已对占用单元格列表进行了排序。
这是可能的编码方式：
def get_random_position(n, occupied_positions):
rnd = random.randint(0, n*n - 1 - len(occupied_positions))
for (row, col) in occupied_positions:
if rnd < row*n+col:
break
rnd += 1
return (rnd // n, rnd % n)
该代码在O（k）中运行，其中k是occupied_positions列表的大小。如果我们不能保证此列表已排序，则需要首先对其进行排序，然后再确定总体时间复杂度，即O（klogk）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句