Kth Largest Element in an Array
لديك مصفوفة من الأعداد الصحيحة nums وعدد صحيح k. أَعِد القيمة الأكبر رقم k في nums: القيمة في الموضع k، عند العد بدءًا من 1، بعد ترتيب المصفوفة من الأكبر إلى الأصغر.
تُحتسب القيم المتساوية كلٌّ على حدة. في [5, 5, 1] تكون أكبر قيمة هي 5، وثاني أكبر قيمة هي أيضًا 5.
الدالة
- numsinteger-array
- القيم المطلوب ترتيبها
- kinteger
- أيّ أكبر قيمة تُعاد، و1 تعني الأكبر
- تُرجعinteger
- القيمة الأكبر رقم k، مع احتساب القيم المكررة
القيود
1 ≤ k ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104- تُعَدّ القيم المتساوية قيمًا منفصلة.
أمثلة
- المدخلات
- nums = [7, 2, 9, 4, 9, 1]k = 2
- المخرجات
- 9
- الشرح
- من الأكبر إلى الأصغر، القيم هي
9, 9, 7, 4, 2, 1. يُحتسب العددان 9 كلٌّ على حدة، لذا فإن ثاني أكبر قيمة هي9، وليست7.
- المدخلات
- nums = [5, -3, 8, 0, 2]k = 4
- المخرجات
- 0
- الشرح
- من الأكبر إلى الأصغر، القيم هي
8, 5, 2, 0, -3، والرابع منها هو0.
- المدخلات
- nums = [6]k = 1
- المخرجات
- 6
- الشرح
- عندما تكون لدينا قيمة واحدة و
k = 1، تكون تلك القيمة هي الأكبر.
سؤال إضافي
تصل القيم الآن واحدة تلو الأخرى. هل يمكنك الإبلاغ عن وسيط جميع القيم التي وصلت حتى الآن بعد كل وصول، في زمن O(log n) لكل قيمة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
عند الترتيب من الأكبر إلى الأصغر، تكون الإجابة في موضع معروف. أيّ موضع؟ وهل تحتاج إلى كل القيم الأخرى لتعرف ذلك؟
القيمة الأكبر ذات الترتيب
kهي الأصغر بين أكبرkقيم. إذا احتفظتَ بأكبرkقيم رأيتها حتى الآن فقط، فأيٌّ منها تقارن به قيمة جديدة؟احتفظ بكومة صغرى تضم بحد أقصى
kمن القيم. تحل قيمة جديدة محل العنصر الأعلى عندما تكون أكبر منه، ويكون العنصر الأعلى في النهاية هو الإجابة. للحصول على زمن متوسط قدرهO(n)، قسّم حول محور عشوائي كما تفعل خوارزمية الترتيب السريع، واحتفظ بالجانب الذي يحتوي على الفهرسn-kفقط.
الحل
إن الفرز وقراءة موضع واحد يجيبان عن السؤال، وهما سريعان بما يكفي هنا. ما يريد القائم بالمقابلة رؤيته هو مقدار الترتيب الذي يمكنك تخطيه، لأنك تحتاج إلى موضع واحد، وليس جميع المواضع n. تحتفظ كومة صغرى بحجم k بالقيم التي لا يزال من الممكن أن تكون هي الإجابة فقط، ويقسّم quickselect العناصر كما يفعل quicksort، لكنه يتبع الجانب الذي يحتوي على الإجابة فقط، ما يخفض متوسط الزمن إلى O(n).
رتّب واقرأ موضعًا واحدًا
الفكرة
تُحدَّد القيمة الأكبر في المرتبة k وفق الترتيب بعد الفرز، لذا رتّب القيم. عند الفرز من الأكبر إلى الأصغر، تصبح [7, 2, 9, 4, 9, 1] هي [9, 9, 7, 4, 2, 1]، وتقع القيمة الأكبر في المرتبة k عند الفهرس k-1. عندما تكون k = 2، يكون ذلك الفهرس 1، أي القيمة 9 الثانية. إذا كان الفرز يضع الأصغر أولًا، فاقرأ الفهرس n-k بدلًا من ذلك: الفهرس 4 في [1, 2, 4, 7, 9, 9] يحتوي على القيمة 9 نفسها.
لا تحتاج القيم المكررة إلى معالجة خاصة: فالفرز يُبقي على كل نسخة، وتشغل كل نسخة موضعًا خاصًا بها.
عندما يكون n = 10^4، يُجري الفرز نحو n log n ≈ 1.3 × 10^5 مقارنة، وهذا يكفي لاجتياز جميع الاختبارات. والهدر هنا هو ترتيب جميع القيم n بينما لا يهم سوى موضع واحد. النهجان التاليان يقللان هذا العمل.
الخوارزمية
- انسخ
numsحتى تظل مصفوفة المستدعي كما هي. - رتّب النسخة. استخدم مقارنة عددية؛ فبعض اللغات تقارن الأعداد كنصوص افتراضيًا.
- أعِد الفهرس
k-1في ترتيب تنازلي، أو الفهرسn-kفي ترتيب تصاعدي.
def findKthLargest(nums, k):
# Largest first: the k-th largest sits at index k-1.
ordered = sorted(nums, reverse=True)
return ordered[k - 1]احتفظ بأكبر k عناصر في كومة صغرى
الفكرة
القيمة الأكبر ذات الترتيب k هي الأصغر بين أكبر k قيم. لذا مرّ على nums مرة واحدة، واحتفظ فقط بأكبر k قيم رأيتها حتى الآن في كومة صغرى. قمة الكومة الصغرى هي أصغر قيمة فيها، وهي بالضبط القيمة المرشحة للإجابة.
عندما تصل قيمة x وتحتوي الكومة على أقل من k قيم، أضِفها. وإلا فقارن x بالقمة. إذا لم تكن x أكبر، فهناك على الأقل k قيم احتفظت بها تساوي x أو تزيد عليها، لذا لا يمكن أن تكون x هي الإجابة أبدًا، فتجاوزها. أما إذا كانت x أكبر، فتكون القمة قد خرجت من بين أكبر k قيم: استبدلها بـ x. في المثال 2 مع k = 4، تملأ القيم الأربع الأولى الكومة بالقيم 5, -3, 8, 0، وتكون القمة -3. ثم تتغلب 2 على -3 وتحل محلها، فتصبح القمة 0، وتكون 0 هي الإجابة.
تتطلب كل قيمة عملية كومة واحدة على الأكثر بتعقيد O(log k)، لذا يكون التعقيد الإجمالي O(n log k) زمنيًا وO(k) من الذاكرة. وهذا أفضل من الفرز عندما تكون k صغيرة، كما أنه يعمل مع تدفق البيانات: فلا تحتاج أبدًا إلى جميع القيم دفعة واحدة. تتضمن Python المكتبة heapq، وJava الصنف PriorityQueue، وC++ البنية priority_queue مع greater، وGo الحزمة container/heap، وRust البنية BinaryHeap مع Reverse، وPHP الصنف SplMinHeap. يكتب الكود الخاص باللغات الأخرى الكومة في مصفوفة، حيث يقع ابنا الفهرس i عند 2i+1 و2i+2، أو عند 2i و2i+1 في Lua وR، اللتين تبدآن العد من 1.
الخوارزمية
- ابدأ بكومة صغرى فارغة.
- لكل قيمة
x، أضِفها ما دامت الكومة تحتوي على أقل منkقيم. - بمجرد أن تحتوي على
kقيم، استبدل العنصر الأعلى بـxفقط عندما تكونxأكبر من العنصر الأعلى. - بعد القيمة الأخيرة، أعد العنصر الأعلى في الكومة.
import heapq
def findKthLargest(nums, k):
# A min-heap of the k largest values so far; its top is the smallest of them.
heap = []
for x in nums:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x) # drop the top, add x
return heap[0]خوارزمية Quickselect باستخدام تقسيم ثلاثي الاتجاهات
الفكرة
يختار Quicksort محورًا ويقسّم العناصر: القيم الأصغر إلى يساره، والقيم الأكبر إلى يمينه. بعد تقسيم واحد، يستقر المحور في فهرسه النهائي بعد الترتيب، حتى وإن لم يكن أيٌّ من الجانبين مرتبًا بعد. يستفيد Quickselect من هذه الحقيقة. عند الترتيب من الأصغر إلى الأكبر، تكون الإجابة عند الفهرس target = n-k. بعد التقسيم، يكون target إما إلى يسار المحور، أو عنده، أو إلى يمينه، لذا تتابع البحث في أحد الجانبين وتتجاهل الآخر.
بالنسبة إلى [7, 2, 9, 4, 9, 1] وk = 2، يكون target هو 6-2 = 4. قسّم حول 4: يشغل 2 و1 الفهرسين 0 و1، ويشغل 4 الفهرس 2، وتشغل 7, 9, 9 الفهارس من 3 إلى 5. يقع الفهرس 4 إلى اليمين، لذا تحتفظ فقط بالفهرس من 3 إلى 5. قسّم هذه العناصر حول 9: يشغل 7 الفهرس 3، وتشغل قيمتا 9 الفهرسين 4 و5. يحتوي الفهرس 4 على 9، لذا فالإجابة هي 9.
استخدم تقسيمًا ثلاثيًّا: القيم الأصغر من المحور، ثم القيم المساوية له، ثم القيم الأكبر منه، مع تتبّعها باستخدام lt وgt. يكون الجزء المتساوي [lt, gt] في موضعه المرتب، لذا إذا وقع target داخله تكون قد انتهيت. باستخدام تقسيم عادي ثنائي الاتجاه، يتقلص مصفوفة تحتوي على 10^4 نسخة من 7 بمقدار قيمة واحدة في كل جولة، أي نحو 5 × 10^7 خطوة؛ أما النسخة ثلاثية الاتجاه فتجيب عنها في مرور واحد.
اختر المحور عشوائيًا. في نصف الحالات، يقع في النصف الأوسط من النطاق، ما يقلّص النطاق إلى ثلاثة أرباع حجمه على الأكثر، لذا يكون العمل المتوقع بضع مرات مرور على n قيمة: O(n). تظل أسوأ حالة هي O(n²) إذا كان كل محور قيمة متطرفة، كما أن اختيارًا ثابتًا، مثل العنصر الأول، يؤدي إلى هذه الحالة عند إدخال مصفوفة مرتبة. يعمل الكود على نسخة، ما يكلّف ذاكرة O(n)؛ أما تقسيم nums نفسها فيجعل استهلاك الذاكرة O(1) إذا كان بإمكانك تغيير المدخل.
الخوارزمية
- انسخ
numsإلىa، واضبطtarget = n-kوlo = 0وhi = n-1. - اختر محورًا عشوائيًا من
a[lo..hi]. - قسّم
a[lo..hi]إلى قيم أصغر من المحور، ومساوية له، وأكبر منه، مع إبقاء القيم المساوية فيa[lt..gt]. - إذا كان
target < lt، فاضبطhi = lt-1؛ وإذا كانtarget > gt، فاضبطlo = gt+1؛ وإلا فأعِد المحور. - كرّر بدءًا من الخطوة 2.
import random
def findKthLargest(nums, k):
a = list(nums)
target = len(a) - k # the answer's index once a is sorted smallest first
lo, hi = 0, len(a) - 1
while True:
pivot = a[random.randint(lo, hi)]
# Three-way partition of a[lo..hi]: < pivot, then == pivot, then > pivot.
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif a[i] > pivot:
a[i], a[gt] = a[gt], a[i]
gt -= 1
else:
i += 1
# Now a[lt..gt] all equal pivot, and they are in their sorted places.
if target < lt:
hi = lt - 1
elif target > gt:
lo = gt + 1
else:
return pivot
أخطاء شائعة وحالات حدّية
تأتي معظم الإجابات الخاطئة من العناصر المكررة ومن الخلط بين طريقتَي عدّ المواضع.
- إزالة العناصر المكررة أولًا. تحتسب المسألة كل نسخة: في
[7, 2, 9, 4, 9, 1]معk = 2، الإجابة هي9، لكن بعد تحويل المصفوفة إلى مجموعة تصبح7. - قراءة الفهرس الخطأ. يبدأ عدّ
kمن 1، لذا تكون الإجابة عند الفهرسk-1في ترتيب تنازلي، وعند الفهرسn-kفي ترتيب تصاعدي، وليسn-k-1. - ترتيب الأعداد كنصوص. في JavaScript وTypeScript، تعطي
[10, 9, 2].sort()النتيجة[10, 2, 9]. مرّر(a, b) => a - b. - استخدام كومة عظمى بحجم
k. يؤدي إخراج أكبر قيمة إلى الاحتفاظ بأصغرkقيم وإرجاع القيمة ذات الترتيبkمن الأصغر. - استخدام Quickselect مع تقسيم ثنائي الاتجاه أو محور ثابت. تؤدي كثرة القيم المتساوية أو المصفوفة المرتبة إلى كلفة
O(n²)، وهذا ما تتضمنه الاختبارات الكبيرة.
أسئلة شائعة4
ما هو التعقيد الزمني لإيجاد العنصر الأكبر رقم K في مصفوفة؟
يستغرق الفرز زمنًا قدره O(n log n). تستغرق الكومة الصغرى ذات الحجم k زمنًا قدره O(n log k) وتستهلك ذاكرة قدرها O(k). يستغرق التحديد السريع باستخدام محور ارتكاز عشوائي زمنًا قدره O(n) في المتوسط وO(n²) في أسوأ الحالات، وهو أمر يجعل محور الارتكاز العشوائي حدوثه غير مرجح جدًا.
لماذا نستخدم كومة صغرى، وليس كومة كبرى، للعثور على العنصر الأكبر رقمًا k؟
تخزّن الكومة أكبر k قيم شوهدت حتى الآن، والقيمة التي يجب مقارنتها وإزالتها هي أصغرها. تحتفظ الكومة الصغرى بهذه القيمة في الأعلى. لا تعمل الكومة الكبرى إلا إذا وضعت فيها القيم n كلها وأزلت عنصرًا k-1 مرة، وهذا يتطلب ذاكرة O(n).
هل أستخدم كومة أم خوارزمية quickselect للعثور على العنصر الأكبر رقم k؟
تكون خوارزمية Quickselect أسرع في المتوسط، O(n)، لكنها تحتاج إلى وجود جميع القيم في الذاكرة وتعيد ترتيبها. تعقيد الكومة هو O(n log k) ولا توجد لها حالة أسوأ سيئة، وتعمل عندما تصل القيم واحدة تلو الأخرى ولا يمكنك تخزينها كلها. في مقابلة، اشرح الطريقتين واكتب الشيفرة للطريقة التي يطلبها السؤال اللاحق.
هل يمكن العثور على العنصر الأكبر من المرتبة k في زمن خطي في أسوأ الحالات؟
نعم. تختار قاعدة الوسيط بين الوسطاء محورًا مضمونًا أن يستبعد نسبة ثابتة من القيم، ما يجعل عملية الاختيار O(n) في أسوأ الحالات، رغم أنها أبطأ عمليًا من اختيار محور عشوائي. وبما أن القيم محصورة بين -10^4 و10^4، يمكنك أيضًا عدّ مرات ظهور كل قيمة، ثم البدء من 10^4 والنزول حتى تتجاوز k من القيم، وذلك في زمن O(n + 2 × 10^4).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def findKthLargest(nums, k):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
nums = [7, 2, 9, 4, 9, 1] k = 2
الإخراج المتوقع
9