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. ومن بين النقاط المتعادلة، إحداثي x للنقطة(-1, 1)هو الأصغر، وتأتي النقطة(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الأولى. - لكل نقطة لاحقة، قارنها بأعلى الكومة: إذا كان ترتيبها أسبق، فاستبدل بها العنصر الأعلى ثم أنزلها في الكومة؛ وإلا فتجاوزها.
- أزِل العنصر الأعلى
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 نقاط إلى نقطة الأصل؟
يستغرق فرز جميع النقاط 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]]