สมมติว่าเรามีชุดของจุดที่กำหนดในอาร์เรย์ที่เรียกว่า 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
-
เล็กที่สุด :=อนันต์
-
สำหรับแต่ละ p ใน pts ทำ
-
ถ้า p[0] เหมือนกับ x หรือ p[1] เหมือนกับ y แล้ว
-
dist :=|x - p[0]| + |y - p[1]|
-
ถ้า dist <น้อยที่สุด แล้ว
-
idx :=ดัชนีของ p เป็น pts
-
เล็กที่สุด :=dist
-
-
มิฉะนั้นเมื่อ dist เท่ากับที่เล็กที่สุดแล้ว
-
ถ้าดัชนีของ p เป็น pts
-
idx :=ดัชนีของ p เป็น pts
-
เล็กที่สุด :=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
