K Closest Points to Origin
נתונות לך n נקודות במישור: נקודה i היא (xs[i], ys[i]). החזר את k הנקודות הקרובות ביותר לראשית הצירים (0, 0), כל אחת כזוג [x, y].
סדר את התשובה לפי המרחק מראשית הצירים, מהקרובה ביותר תחילה. נקודות שנמצאות במרחק זהה יופיעו בסדר עולה לפי x, ואז לפי y. נקודה שמופיעה יותר מפעם אחת נספרת פעם אחת לכל עותק.
פונקציה
- xsinteger-array
- קואורדינטת ה־x של כל נקודה
- ysinteger-array
- קואורדינטת ה־y של כל נקודה
- kinteger
- כמה נקודות להחזיר
- מחזירהinteger-2d-array
- k הנקודות הקרובות ביותר כזוגות [x, y], מהקרובה ביותר והלאה; במקרה של שוויון, לפי x ואז לפי y
אילוצים
n == xs.length == ys.length1 ≤ k ≤ n ≤ 5000-104 ≤ xs[i], ys[i] ≤ 104- נקודות עשויות לחזור; כל עותק הוא נקודה נפרדת.
דוגמאות
- קלט
- xs = [3, -1, 2, 0]ys = [1, 2, -2, 5]k = 2
- פלט
- [[-1, 2], [2, -2]]
- הסבר
- המרחקים בריבוע הם 10, 5, 8 ו־25. שני הקטנים ביותר שייכים ל־
(-1, 2)עם 5 ול־(2, -2)עם 8, בסדר הזה.
- קלט
- xs = [1, -1, 0, 1]ys = [1, 1, 2, -1]k = 3
- פלט
- [[-1, 1], [1, -1], [1, 1]]
- הסבר
- לנקודות
(1, 1),(-1, 1)ו־(1, -1)יש מרחק בריבוע 2, ולנקודה(0, 2)יש מרחק בריבוע 4. מבין הנקודות שיש ביניהן תיקו, ל־(-1, 1)יש ערך x הקטן ביותר, ו־(1, -1)מופיעה לפני(1, 1)לפי y.
- קלט
- xs = [7]ys = [-7]k = 1
- פלט
- [[7, -7]]
- הסבר
- יש רק נקודה אחת, ואתה צריך אחת, לכן התשובה היא
(7, -7)עצמה.
שאלת המשך
הנקודות מגיעות כעת אחת בכל פעם, ולאחר כל אחת מהן עליך לדווח על k הנקודות הקרובות ביותר עד כה. כמה זיכרון אתה צריך?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
אתה אף פעם לא צריך את המרחק עצמו. מה אפשר להשוות במקום
√(x² + y²)ועדיין לקבל את אותו סדר?נניח ששומרים את
kהנקודות הקרובות ביותר שנראו עד כה. מול איזו מהן מתחרה נקודה חדשה?שמרו ערימת מקסימום של לכל היותר
kנקודות המסודרות לפי(x² + y², x, y). החליפו את האיבר העליון כשנקודה חדשה קודמת לו, ובסוף הוציאו את הנקודות מהערימה כדי למלא את התשובה מהסוף.
פתרון
אין צורך בשורש ריבועי לחישוב המרחק: x² + y² נותן את אותו סדר ונשאר מספר שלם. דרושים לך רק k מתוך n הנקודות, ולכן ערימת מקסימום של k הנקודות הקרובות ביותר עד כה, כשהנקודה הרחוקה ביותר נמצאת בראש ומוכנה להחלפה, עולה O(n log k) במקום מיון מלא.
בחרו את הנקודה הקרובה ביותר k פעמים
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
הנקודה הראשונה בתשובה היא הקרובה ביותר מכולן, השנייה היא הקרובה ביותר מבין הנותרות, וכן הלאה. לכן סרוק את הנקודות k פעמים, ובכל פעם בחר את הנקודה שמופיעה ראשונה לפי (x² + y², x, y) מבין אלה שעדיין לא נבחרו.
בכל סריקה נוגעים בכל n הנקודות. עבור n = 5000 ו-k = 2500, מדובר ב-1.25 × 10^7 השוואות תלת-חלקיות.
אלגוריתם
- סמן כל נקודה כלא נבחרת.
- חזור על הפעולה
kפעמים: סרוק את הנקודות שלא נבחרו ומצא את הנקודה שמופיעה ראשונה לפי(x² + y², x, y). - סמן אותה כנבחרת והוסף את
[x, y]לתשובה. - החזר את התשובה.
def kClosest(xs, ys, k):
n = len(xs)
taken = [False] * n
result = []
for _ in range(k):
best = -1
for i in range(n):
# Compare (squared distance, x, y): the order the answer uses.
if not taken[i] and (best == -1 or
(xs[i] * xs[i] + ys[i] * ys[i], xs[i], ys[i]) <
(xs[best] * xs[best] + ys[best] * ys[best], xs[best], ys[best])):
best = i
taken[best] = True
result.append([xs[best], ys[best]])
return resultמיין כל נקודה
האינטואיציה
התשובה היא k הנקודות הראשונות בסדר המלא, לכן מיין את כל הנקודות לפי (x² + y², x, y) והשאר את k הראשונות. בדוגמה 1 המפתחות הממוינים הם (5, -1, 2), (8, 2, -2), (10, 3, 1) ו-(25, 0, 5), והשניים הראשונים נותנים את התשובה.
המיון עולה O(n log n) בלי קשר לערך של k. כש-k קטן, רוב העבודה הזאת מסדרת נקודות שלעולם לא יגיעו לתשובה.
אלגוריתם
- בנה מפתח עבור כל נקודה
(x² + y², x, y). - מיין את הנקודות לפי המפתח.
- החזר את
kהראשונות שבהן כזוגות[x, y].
def kClosest(xs, ys, k):
points = list(zip(xs, ys))
# Sort by squared distance, then x, then y: the order the answer uses.
points.sort(key=lambda p: (p[0] * p[0] + p[1] * p[1], p[0], p[1]))
return [[x, y] for x, y in points[:k]]שמירה על k הקרובים ביותר בערמת מקסימום
האינטואיציה
שמור את k הנקודות הטובות ביותר שנראו עד כה. נקודה חדשה יכולה להוציא רק את הנקודה השמורה שמדורגת אחרונה, לכן שמור את הנקודות השמורות בערימת מקסימום לפי (x² + y², x, y), כשהנקודה הזאת נמצאת בראשה. לאחר שנשמרות k נקודות, נקודה שמדורגת לפני הנקודה שבראש הערימה מחליפה אותה; כל נקודה אחרת מושלכת, כי k הנקודות השמורות כבר מדורגות לפניה.
בדוגמה 2 עם k = 3, בראש הערימה אחרי שלוש הנקודות הראשונות נמצאת (0, 2) עם המפתח (4, 0, 2). לנקודה (1, -1) יש את המפתח (2, 1, -1), היא מדורגת לפניה ומחליפה אותה.
ערימה ממוינת רק באופן חלקי, לכן הסר את הנקודה שבראש הערימה k פעמים ומלא את התשובה מהמשבצת האחרונה שלה ועד הראשונה. כל נקודה דורשת לכל היותר שלב ערימה אחד של O(log k), לכן זמן הריצה הוא O(n log k) והזיכרון הוא O(k).
אלגוריתם
- יוצרים ערימה מקסימלית ריקה לפי המפתח
(x² + y², x, y). - מכניסים כל אחת מ־
kהנקודות הראשונות. - עבור כל נקודה מאוחרת יותר, משווים אותה לראש: אם היא מדורגת לפניו, מחליפים אותה איתו ומבצעים sift down; אחרת מדלגים עליה.
- מסירים את הראש
kפעמים; כל נקודה שהוסרה ממלאת את המקום הפנוי האחרון בתשובה. - מחזירים את התשובה.
import heapq
def kClosest(xs, ys, k):
# heapq is a min-heap; negating every part of (distance, x, y) puts the
# farthest kept point, in the answer's order, on top.
heap = []
for x, y in zip(xs, ys):
item = (-(x * x + y * y), -x, -y)
if len(heap) < k:
heapq.heappush(heap, item)
elif item > heap[0]:
# The new point comes before the farthest kept one: swap them.
heapq.heapreplace(heap, item)
# Popping gives the farthest first, so fill the answer from the back.
result = [None] * len(heap)
for i in range(len(result) - 1, -1, -1):
_, x, y = heapq.heappop(heap)
result[i] = [-x, -y]
return result
מלכודות ומקרי קצה
- דילוג על שובר השוויון. בדוגמה 2 יש שלוש נקודות במרחק 2; בלי להשוות את
xואז אתy, הן יופיעו בסדר הקלט במקום בסדר(-1, 1),(1, -1),(1, 1). - שמירה על ערימת מינימום של
kנקודות. הנקודה שבראש הערימה היא הקרובה ביותר, ולכן כל הוצאה מסלקת נקודה שהתשובה זקוקה לה, ובסוף נשארות לךkהנקודות הרחוקות ביותר. - קריאת התשובה ישירות ממערך הערימה. המערך הזה מסודר רק באופן חלקי; קודם כול יש להוציא את הנקודות בזו אחר זו.
- הסרת נקודות כפולות. אם הנקודה
(5, 5)מופיעה שלוש פעמים ו-k = 3, התשובה היא אותה נקודה שלוש פעמים.
שאלות נפוצות4
מהי סיבוכיות הזמן של K Closest Points to Origin?
מיון כל הנקודות נמשך O(n log n). גרסת הערימה דורשת O(n log k) עבור הסריקה ועוד O(k log k) כדי לסדר את k הנקודות שנותרו, והיא שומרת בזיכרון רק O(k) נקודות.
למה להשתמש בערימת מקסימום ולא בערימת מינימום עבור k הנקודות הקרובות ביותר?
נקודה חדשה מתחרה בנקודה הרחוקה ביותר מבין k הנקודות שנשמרו, ולכן הנקודה הזאת חייבת להיות בראש הערימה. ערימת מינימום עובדת רק אם היא מכילה את כל n הנקודות, כך שאפשר להסיר את k הנקודות הקרובות ביותר, פעולה שצורכת זיכרון של O(n) במקום O(k).
האם צריך את השורש הריבועי כדי להשוות מרחקים?
לא. עבור מספרים שאינם שליליים, a < b בדיוק כאשר √a < √b, ולכן x² + y² נותן אותו סדר כמו המרחק. הוא גם נשאר מספר שלם: לכל היותר 2 × 10^8 כאן, בתוך הטווח של 32 סיביות.
האם אפשר לפתור את בעיית K הנקודות הקרובות ביותר לראשית בזמן O(n)?
בממוצע, כן. Quickselect מחלק את הנקודות סביב ציר אקראי לפי אותו סדר (x² + y², x, y) וממשיך רק בצד שמכיל את המיקום k, בזמן O(n) בממוצע. k הנקודות שמשמאל למיקום הזה הן התשובה; מיון שלהן מוסיף O(k log k).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def kClosest(xs, ys, k):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
xs = [3, -1, 2, 0] ys = [1, 2, -2, 5] k = 2
הפלט הצפוי
[[-1, 2], [2, -2]]