数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 Python 查找具有相同 x 或 y 坐标的最近点的程序
假设我们在一个名为 pts 的数组中给定了一组点。我们还有另一个点 (x, y)，它是我们当前的位置。我们将有效点定义为与我们当前点共享相同 x 坐标或相同 y 坐标的点。我们必须返回有效点在当前位置 (x, y) 的曼哈顿距离最小的索引。如果有多个点，则返回索引最小的有效点。（注意：两点 (a, b) 和 (p, q) 之间的曼哈顿距离为 |a - p| + |b - q|。）
因此，如果输入类似于 pts = [(1,2),(3,1),(3,4),(2,3),(4,4)] pt = (2,4)，则输出将为 2，因为有两个最近的点 (3,4) 和 (2,3)，但 (3,4) 的索引较小。
为了解决这个问题，我们将遵循以下步骤：
x, y := pt
idx := -1
smallest := 无限大
对于 pts 中的每个点 p，执行以下操作：
如果 p[0] 与 x 相同或 p[1] 与 y 相同，则：
dist := |x - p[0]| + |y - p[1]|
如果 dist < smallest，则：
idx := p 在 pts 中的索引
smallest := dist
否则，当 dist 等于 smallest 时：
如果 p 在 pts 中的索引 < idx，则：
idx := p 在 pts 中的索引
smallest := dist
返回 idx
让我们看看以下实现以更好地理解：
示例
def solve(pts, pt):
x, y = pt
idx = -1
smallest = float("inf")
for p in pts:
if p[0] == x or p[1] == y:
dist = abs(x - p[0]) + abs(y - p[1])
if dist < smallest:
idx = pts.index(p)
smallest = dist
elif dist == smallest:
if pts.index(p) < idx:
idx = pts.index(p)
smallest = dist
return idx
pts = [(1,2),(3,1),(3,4),(2,3),(4,4)]
pt = (2,4)
print(solve(pts, pt))输入
[(1,2),(3,1),(3,4),(2,3),(4,4)], (2,4)
输出
2
更新于： 2021年5月29日
2K+ 次浏览
广告