Kth Largest Element in a Stream
يبدأ تدفق من الأعداد الصحيحة بالقيم الموجودة في nums. ثم تصل قيم adds واحدة تلو الأخرى. بعد كل وصول، سجّل القيمة الأكبر رقم k بين كل القيم التي ظهرت حتى الآن، مع احتساب القيم المتساوية كلٌّ على حدة. أعد القيم المسجّلة بالترتيب، قيمةً واحدة لكل قيمة في adds.
يحتوي nums على k-1 قيمة على الأقل، لذا يوجد دائمًا بعد الوصول الأول k قيم على الأقل للاختيار من بينها.
الدالة
- kinteger
- الرتبة المطلوب الإبلاغ عنها، حيث تشير 1 إلى أكبر قيمة
- numsinteger-array
- القيم الموجودة بالفعل في مجرى البيانات
- addsinteger-array
- القيم التي تصل، بالترتيب
- تُرجعinteger-array
- القيمة ذات الترتيب k تنازليًا بعد كل وصول
القيود
1 ≤ nums.length ≤ 1041 ≤ adds.length ≤ 1041 ≤ k ≤ nums.length + 1-104 ≤ nums[i], adds[i] ≤ 104numsيمكن أن تكون بأي ترتيب، وتُعدّ القيم المتساوية قيمًا منفصلة.
أمثلة
- المدخلات
- k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
- المخرجات
- [3, 5, 6, 6, 7]
- الشرح
- بعد 3، يكون ثالث أكبر عدد من بين 7 و5 و3 و1 هو 3. ثم يرفعه 9 إلى 5، ويرفعه 6 إلى 6، ولا يغيّر 2 شيئًا، ويرفعه 8 إلى 7 (9، 8، 7).
- المدخلات
- k = 1nums = [-2]adds = [-5, 0, -1, 4]
- المخرجات
- [-2, 0, 0, 4]
- الشرح
- عندما تكون
k = 1، تكون الإجابة هي أكبر قيمة حتى الآن: -2 إلى أن تظهر 0، وتظل 0 بعد -1، ثم تصبح 4.
- المدخلات
- k = 4nums = [6, 6, 2]adds = [6, 1, 9]
- المخرجات
- [2, 2, 6]
- الشرح
- يُنتج الوصول الأول أربع قيم: 6 و6 و6 و2، لذا فإن رابع أكبر قيمة هي 2، ولا يغيّرها 1. بعد 9، تكون أكبر أربع قيم هي 9 و6 و6 و6: تُحتسب كل نسخة من 6.
سؤال إضافي
كيف ستجيب عن السؤال نفسه إذا كان بالإمكان أيضًا إزالة القيم من التدفق؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
يعطي ترتيب كل شيء بعد كل وصول الإجابة الصحيحة، لكنه يعيد تقريبًا كل العمل في كل مرة. ما القيم التي لا يزال من الممكن أن تصبح القيمة رقم
kمن الأكبر لاحقًا؟تصل القيم ولا تغادر أبدًا. بمجرد أن يكون هناك
kقيم أكبر منها، لا يمكن أن تكون الإجابة مرة أخرى. ما عليك سوى الاحتفاظ بأكبرkقيم شوهدت حتى الآن.احتفظ بتلك القيم
kفي كومة صغرى. تكون أصغر قيمة بينها في أعلاها، وهي القيمة ذات الترتيبkمن الأكبر إجمالًا. عند وصول قيمة، أضِفها ما دامت الكومة تحتوي على أقل منkقيم؛ بعد ذلك، استبدل القيمة في الأعلى فقط عندما تكون القيمة الجديدة أكبر.
الحل
لا تغادر القيمُ التيارَ أبدًا، لذا فإن أي قيمة تقل عن القيمة الحالية التي تحتل المرتبة k بين الأكبر تُستبعَد نهائيًا. احتفِظ بأكبر k قيمة في كومة صغرى: قمتها هي الإجابة، وتكلّف كل قيمة تصل مقارنةً واحدةً وتحديثًا واحدًا للكومة على الأكثر، بتعقيد O(log k).
رتّب بعد كل وصول
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
احتفظ بكل قيمة في قائمة. بعد كل وصول، رتّبها ترتيبًا تصاعديًا واقرأ الفهرس length-k، فهو العنصر الأكبر رقم k بحكم التعريف.
يرتّب كل وصول ما يصل إلى n + m قيمة، حيث إن n وm هما طولا nums وadds. ومع وجود 10^4 من كل منهما، يكون المجموع نحو 2 × 10^9 مقارنة.
الخوارزمية
- انسخ
numsإلى قائمةvalues. - لكل قيمة من
adds، ألحِقها بـvalues. - رتّب
valuesبترتيب تصاعدي وسجّلvalues[length-k]. - أعِد القيم المسجّلة.
def kthLargestStream(k, nums, adds):
values = list(nums)
result = []
for x in adds:
values.append(x)
values.sort()
# In increasing order the k-th largest sits k places from the end.
result.append(values[len(values) - k])
return resultكومة صغرى لأكبر k قيم
الفكرة
بمجرد أن تصبح هناك k قيم أكبر من قيمة ما، يظل ذلك صحيحًا لبقية التدفق، لذا لا تهم سوى أكبر k قيم شوهدت حتى الآن. خزّنها في كومة صغرى. عنصرها الأعلى هو الأصغر بين أكبر k قيم، وهو بالضبط القيمة ذات الترتيب k من الأكبر إجمالًا.
عندما تصل x وتكون الكومة ممتلئة، فقارنها بالعنصر الأعلى. إذا لم تكن x أكبر، فهي ليست ضمن أكبر k قيم ولا يتغير شيء. وإذا كانت أكبر، يُستبعد العنصر الأعلى: استبدله بـ x ثم أعد ترتيب الكومة نزولًا، في O(log k). تمر القيم الابتدائية بالإجراء نفسه، لذا قد يكون nums أطول من k.
في المثال الأول، تحتوي الكومة على 7 و1 و5 بعد nums، ويكون 1 في الأعلى. تحل القيمة الوافدة 3 محل 1، ويكون العنصر الأعلى، 3، هو الإجابة الأولى.
الخوارزمية
- ابدأ بكومة صغرى فارغة.
- لإضافة
x: إذا كانت الكومة تحتوي على أقل منkقيم، فأضفxإليها. وإلا، إذا كانتxأكبر من القيمة العليا، فاستبدل القيمة العليا بـxواستعد ترتيب الكومة. - أضف كل قيمة من
numsبهذه الطريقة. - لكل قيمة من
adds، أضفها وسجّل القيمة العليا في الكومة. - أعِد القيم المسجّلة.
import heapq
def kthLargestStream(k, nums, adds):
# A min-heap of the k largest values so far; heap[0] is the smallest of them.
heap = []
def add(x):
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x) # drop the top, add x
for x in nums:
add(x)
result = []
for x in adds:
add(x)
result.append(heap[0]) # the k-th largest so far
return result
أخطاء شائعة وحالات حدّية
- حذف القيم المكررة. أكبر أربع قيم من 9 و6 و6 و6 و2 هي 9 و6 و6 و6. تُرجع المجموعة، أو عملية التحقق التي تتخطى القيم الموجودة مسبقًا، القيمة 2 في المثال الثالث بدلًا من 6.
- قراءة الإجابة قبل الإضافة. عندما تحتوي
numsعلىk-1قيمة، لا يمتلئ الكومة إلا بعد وصول العنصر الأول، لذا أضِف أولًا، ثم اقرأ القيمة العليا. - العدّ من الطرف الخطأ بعد الفرز. في الترتيب التصاعدي، تقع القيمة الأكبر رقم
kعند الفهرسlength-k؛ أما الفهرسk-1فيحتوي على القيمة الأصغر رقمk. - استخدام ترتيب الكومة الافتراضي. إن
priority_queueفي C++ وBinaryHeapفي Rust كومتان عظميان: مرّرgreater<int>أو غلّف القيم فيReverse.
أسئلة شائعة3
لماذا نستخدم كومة صغرى وليس كومة كبرى لإيجاد العنصر الأكبر رقم k؟
أصغر القيم الأكبر وعددها k هو الإجابة والقيمة التي يجب على الوافد الجديد تجاوزها، وتحافظ كومة صغرى حجمها k على وجوده في القمة. أما كومة عظمى تضم كل قيمة، فتضع الأكبر في القمة، لذا فإن الوصول إلى القيمة ذات الترتيب k يعني إخراج k-1 قيمة ثم إعادتها إلى الكومة عند كل وصول.
ما هو التعقيد الزمني لإيجاد العنصر الأكبر رقم K في تدفّق؟
تكلّف كل عملية وصول O(log k): مقارنة واحدة مع العنصر الأعلى، وعملية ترشيح واحدة على الأكثر عبر كومة تضم k من القيم. يتكلّف إنشاء الكومة من nums مقدار O(n log k)، لذا يستغرق التنفيذ بأكمله O((n + m) log k) من الوقت وO(k) من المساحة الإضافية.
هل يمكن حل مسألة العنصر الأكبر رقم K في تدفّق باستخدام قائمة مرتبة؟
نعم. أبقِ جميع القيم مرتبة، وأدرج كل قيمة تصل في موضعها باستخدام البحث الثنائي، واقرأ القيمة التي تبعد k مواضع عن النهاية. يستغرق البحث O(log n)، لكن إزاحة القيم بعد موضع الإدراج تستغرق O(n) لكل قيمة تصل: نحو 1.5 × 10^8 عملية إزاحة لـ 10^4 قيمة ابتدائية و10^4 قيمة تصل.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def kthLargestStream(k, nums, adds):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
k = 3 nums = [7, 1, 5] adds = [3, 9, 6, 2, 8]
الإخراج المتوقع
[3, 5, 6, 6, 7]