Top K Frequent Elements
لديك مصفوفة من الأعداد الصحيحة nums وعدد صحيح k. أعد القيم k الأكثر تكرارًا في nums، بدءًا من الأكثر تكرارًا. عندما تتكرر قيمتان العدد نفسه من المرات، تأتي القيمة الأصغر أولًا.
تظهر كل قيمة مرة واحدة في الإجابة، مهما بلغ عدد مرات ظهورها في nums، ولا يكون k أبدًا أكبر من عدد القيم المختلفة.
الدالة
- numsinteger-array
- القيم المراد عدّها
- kinteger
- كم عدد القيم المطلوب إرجاعها
- تُرجعinteger-array
- أكثر k من القيم تكرارًا، مرتبةً من الأكثر تكرارًا أولًا، وعند التعادل تُقدَّم القيمة الأصغر.
القيود
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ k، وkلا يتجاوز عدد القيم المميزة فيnums.
أمثلة
- المدخلات
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- المخرجات
- [4, 1]
- الشرح
- يتكرر
4أربع مرات، و1ثلاث مرات، بينما يظهر كل من2و3مرة واحدة. القيمتان الأكثر تكرارًا هما4، ثم1.
- المدخلات
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- المخرجات
- [-2, 5]
- الشرح
- تظهر كل من
-2و5و7مرتين، بينما تظهر9مرة واحدة. تتعادل ثلاث قيم في الصدارة، لذا فإن أصغر قيمتين،-2و5، هما الإجابة.
- المدخلات
- nums = [8]k = 1
- المخرجات
- [8]
- الشرح
- توجد قيمة واحدة، لذا فهي الأكثر تكرارًا.
+16 اختبارات مخفية عند الإرسال
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ابدأ بمعرفة عدد مرات ظهور كل قيمة. ما هي بنية البيانات التي تربط كل قيمة بعدد مرات ظهورها في مرور واحد؟
بعد معرفة التكرارات، تريد أفضل
kقيم وفق ترتيب واحد: التكرار الأعلى أولًا، والقيمة الأصغر عند التعادل. يفي ترتيب جميع القيم المتميزة بالغرض. تحتفظ كومة صغرى بحجمkبالقيم التي لا يزال بإمكانها الظهور في الإجابة.العدد هو عدد صحيح من 1 إلى
n. أنشئ دلوًا لكل عدد، بحيث يحتوي الدلوcعلى القيم التي تظهرcمرات بالضبط، ثم اقرأ الدلاء بدءًا من أعلى عدد تكرارات نزولًا. املأ الدلاء بالمرور على القيم من الأصغر إلى الأكبر، وسيكون كل دلو مرتبًا مسبقًا عند التعادل.
الحل
العدّ هو الجزء السريع: مرور واحد باستخدام خريطة تجزئة يحسب عدد مرات ظهور كل قيمة. السؤال الحقيقي هو كيفية اختيار أفضل k قيم دون بذل جهد أكبر مما يلزم. يتطلب ترتيب جميع القيم المميزة وعددها d حسب العدد تكلفة O(d log d)، وتُخفّض كومة صغرى بحجم k ذلك إلى O(d log k)، وبما أن العدد عدد صحيح من 1 إلى n، فإن فرز الدلاء يرتب القيم حسب العدد دون أي مقارنات.
عُدّ، ثم رتّب حسب العدد
الفكرة
ابدأ بالعدّ. تمريرة واحدة باستخدام خريطة تجزئة من القيمة إلى عدد مرات ظهورها تحوّل [4, 1, 4, 2, 1, 4, 3, 1, 4] إلى 4 → 4، 1 → 3، 2 → 1، 3 → 1.
ثم رتّب القيم المميّزة حسب ترتيب الإجابة: العدد الأكبر أولًا، وعند تساوي الأعداد تأتي القيمة الأصغر أولًا. اجعل المقارنة في الفرز مطابقة لذلك تمامًا، بحيث يكون العدد مفتاح المقارنة الأول والقيمة المفتاح الثاني، وتكون أول k عناصر من القائمة المرتّبة هي الإجابة. هنا يكون الترتيب 4, 1, 2, 3، وتُبقي k = 2 على 4 و1.
تكلّف عملية العدّ O(n). ويكلّف فرز القيم المميّزة d مقدار O(d log d)، وبحد أقصى O(n log n) عندما تكون كل القيم مختلفة: يستغرق فرز 10^4 قيمة نحو 1.3 × 10^5 مقارنة، وهذا سريع. لكن الهدر يكمن في أن الفرز يرتّب كل القيم بينما لا تهمّنا سوى أول k منها.
الخوارزمية
- احسب عدد مرات ظهور كل قيمة في خريطة تجزئة.
- ضع القيم المميزة في قائمة.
- رتّب القائمة حسب العدد ترتيبًا تنازليًا، وحسب القيمة ترتيبًا تصاعديًا عند تساوي الأعداد.
- أعِد أول
kقيم.
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Most frequent first; equal counts put the smaller value first.
ordered = sorted(counts, key=lambda value: (-counts[value], value))
return ordered[:k]احتفِظ بأفضل k عناصر في كومة صغرى
الفكرة
أنت تحتاج فقط إلى أفضل k قيم، لذا احتفظ بـk مرشحين فقط. لكل قيمة جديدة، السؤال هو ما إذا كانت تتفوق على أضعف مرشح تحتفظ به؛ والأضعف هو الأقل عددًا، أو الأكبر قيمةً عند تساوي العدد. تحافظ الكومة الصغرى المرتبة وفق هذه القاعدة على أضعف مرشح في القمة، حيث يمكنك قراءته في O(1) واستبداله في O(log k).
مرّ على القيم المتميزة. ما دامت الكومة تحتوي على أقل من k قيم، أضف إليها القيمة. بعد ذلك، استبدل القمة بأي قيمة تتفوق عليها، وتخلّص من أي قيمة لا تتفوق عليها، لأنك تحتفظ بالفعل بـk قيم أفضل. باستخدام كومة من مكتبة، يكون الأمر أقصر إذا أضفت كل قيمة، ثم أزلت قيمة واحدة كلما تجاوز حجم الكومة k، وبذلك تحتفظ بالقيم الـk نفسها.
في النهاية، تحتوي الكومة على الإجابة، لكن ليس بترتيب الإجابة؛ فالكومة مرتبة جزئيًا فقط. تعيد عملية الإزالة أضعف قيمة أولًا، لذا اكتب الإجابة بدءًا من الموضع الأخير وصولًا إلى الأول.
تتطلب كل واحدة من القيم المتميزة البالغ عددها d عملية كومة واحدة على الأكثر ضمن k مدخلات، لذا يستغرق الاختيار O(d log k). وهذا أسرع من الفرز عندما تكون k أصغر بكثير من d، مثل اختيار أفضل 10 من بين 8000 قيمة متميزة.
الخوارزمية
- احسب عدد تكرارات كل قيمة في خريطة تجزئة.
- لكل قيمة مميزة، أضِفها إلى الكومة ما دامت الكومة تحتوي على أقل من
kقيم. - بعد امتلاء الكومة، قارن القيمة بأعلى الكومة، وهي أضعف قيمة محتفَظ بها. إذا كانت القيمة الجديدة أقوى، فضعها في الأعلى ثم أعد ترتيبها نزولًا.
- أزل العناصر من الكومة
kمرات، واكتب كل قيمة في الإجابة بدءًا من الموضع الأخير وصولًا إلى الأول.
import heapq
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Entries are (count, -value). heapq keeps the smallest entry on top, which is
# the weakest value kept: the lowest count, and on a tie the larger value.
heap = []
for value, count in counts.items():
heapq.heappush(heap, (count, -value))
if len(heap) > k:
heapq.heappop(heap)
# Pops come out weakest first, so fill the answer from the back.
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = -heapq.heappop(heap)[1]
return resultعُدّ، ثم رتّب في مجموعات حسب العدد
الفكرة
العدد هنا ليس أي عدد: بل هو عدد صحيح بين 1 وn. وهذا يتيح استخدام فرز الدلاء. أنشئ دلوًا لكل عدد، بحيث يحتوي الدلو c على القيم التي تتكرر c مرات بالضبط، ثم اقرأ الدلاء بدءًا من الدلو n نزولًا. ستظهر القيم بدءًا بالأكثر تكرارًا، ولن تُقارَن أي قيمتين للعدّ أبدًا.
وتتطلب قاعدة التعادل أمرًا إضافيًا: داخل كل دلو، يجب أن تأتي القيمة الأصغر أولًا. تقع القيم بين -10^4 و10^4، لذا يمكن لمصفوفة من R = 2 × 10^4 + 1 عدّادًا أن تتولى العدّ، مع وضع القيمة v عند الفهرس v + 10^4. مرّ على تلك المصفوفة من أصغر قيمة إلى أكبرها، وأضف كل قيمة إلى الدلو الموافق لعدد مرات تكرارها. يمتلئ كل دلو بترتيب تصاعدي، وهو ترتيب التعادل، لذا لا حاجة إلى الفرز مطلقًا.
بالنسبة إلى [5, -2, 7, -2, 7, 5, 9]، يضع المرور القيم -2 و5 و7 في الدلو 2 بهذا الترتيب، ويضع 9 في الدلو 1. وعند القراءة نزولًا من الدلو 7، يكون الدلو 2 أول دلو يحتوي على قيم، ويأخذ k = 2 القيمتين -2 و5.
يتكوّن العمل من مرور واحد على nums، ومرور واحد على عدّادات R، ومرور واحد على الدلاء، أي O(n + R) إجمالًا: تعقيد خطي عند ثبات نطاق القيم. باستخدام خريطة تجزئة بدلًا من مصفوفة العدّ، يظل العدّ خطيًا، لكن الدلاء ستمتلئ بترتيب الخريطة، وستحتاج إلى فرز كل دلو للالتزام بقاعدة التعادل.
الخوارزمية
- احسب عدد مرات ظهور كل قيمة في مصفوفة مفهرسة باستخدام
value + 10^4. - أنشئ مجموعات من 1 إلى
n، قائمة واحدة لكل عدد مرات ظهور ممكن. - مرّ على مصفوفة العدّ من أصغر قيمة إلى أكبر قيمة، وأضف كل قيمة تظهر إلى المجموعة المقابلة لعدد مرات ظهورها.
- اقرأ المجموعات بدءًا من عدد مرات الظهور
nتنازليًا حتى تحصل علىkقيم.
def topKFrequent(nums, k):
OFFSET = 10000 # values run from -10^4 to 10^4
counts = [0] * (2 * OFFSET + 1)
for x in nums:
counts[x + OFFSET] += 1
# buckets[c] lists the values that occur exactly c times. Walking the
# values from smallest to largest fills every bucket in ascending order.
buckets = [[] for _ in range(len(nums) + 1)]
for i, c in enumerate(counts):
if c > 0:
buckets[c].append(i - OFFSET)
# Read the buckets from the highest count down until k values are taken.
result = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
result.append(value)
if len(result) == k:
return result
return result
أخطاء شائعة وحالات حدّية
نادرًا ما يكون العدّ خاطئًا. ترتيب الإجابة هو ما يكون خاطئًا.
- كسر التعادل بحسب الظهور أولًا أو بحسب ترتيب خريطة التجزئة. في المثال الثاني، تظهر القيم
-2و5و7مرتين لكل منها، ولا تجعل[-2, 5]الإجابة الصحيحة الوحيدة سوى قاعدة القيمة الأصغر. - إرجاع مصفوفة الكومة كما هي. الكومة مرتبة جزئيًا فقط، وأعلى قيمة فيها هي الأضعف، أي التي ينبغي أن تأتي أخيرًا.
- عكس قاعدة كسر التعادل في الكومة. من بين قيمتين لهما العدد نفسه من التكرارات، تكون القيمة الأكبر أضعف، لذا فإن استخدام كومة صغرى على
(count, value)يزيل العنصر الخطأ. استخدم(count, -value)أو مقارنة مكتوبة وفقًا للقاعدة. - إنشاء عدد من الدلاء يساوي عدد القيم المتميزة فقط. فقد تتكرر قيمة واحدة
nمرة، كما في[3, 3, 3, 3]، لذا يجب أن يكون الدلوnموجودًا. - في Java، مقارنة عدّادين من النوع
Integerباستخدام!=. فهذا يقارن المراجع، ويؤدي إلى نتائج خاطئة عندما تتجاوز الأعداد 127. حوّلهما أولًا إلىintبإزالة التغليف. - أخذ دلو كامل في النهاية. توقّف بمجرد أن يصبح لديك
kقيم، حتى لو كان ذلك في منتصف دلو.
أسئلة شائعة4
ما هو التعقيد الزمني لإيجاد العناصر الأكثر تكرارًا وعددها K؟
يستغرق العدّ O(n). ثم يتطلب اختيار أعلى k تكلفة O(d log d) عند الفرز على القيم المختلفة البالغ عددها d، وO(d log k) باستخدام كومة صغرى حجمها k، وO(n) بالإضافة إلى مرور واحد على نطاق القيم باستخدام فرز الدلاء. بما أن d قد يصل إلى n، فإن الفرز يستغرق O(n log n) في أسوأ الحالات، بينما يكون فرز الدلاء خطيًا.
هل يمكن حل مسألة أكثر K من العناصر تكرارًا في زمن O(n)؟
نعم، باستخدام فرز الدلاء. الأعداد هي أعداد صحيحة من 1 إلى n، لذا يوضع كل عنصر في الدلو الذي يطابق عدده، وقراءة الدلاء من أعلى عدد إلى أدناه تسرد العناصر حسب التكرار من دون أي فرز بالمقارنة. كما أن التحديد السريع للأعداد يستغرق O(n) في المتوسط، لكن أسوأ حالاته تربيعي.
لماذا نستخدم كومة صغرى وليس كومة كبرى؟
تعمل أيضًا كومة عظمى تضم جميع القيم d: ابنِها في O(d) وأزل عنصرًا منها k مرات، بإجمالي O(d + k log d). تحتفظ كومة صغرى بحجم k بـ k عناصر فقط، وتناسب القيم التي تصل واحدة تلو الأخرى، لأن رأسها هو العنصر المرشّح للإزالة. لكن ثمن ذلك أنها تُخرج الإجابة بترتيب عكسي، لذا تملأ النتيجة بدءًا من الخلف.
كيف تكسر التعادل في مسألة أكثر العناصر تكرارًا ضمن أعلى K؟
اختر قاعدة واحدة وطبّقها في كل مكان؛ هنا، عند تساوي الأعداد، يأتي الأصغر أولًا، مما يجعل الإجابة فريدة. في الترتيب، قارِن الأعداد ثم القيم. في الكومة، من بين قيمتين لهما العدد نفسه، تكون القيمة الأكبر أضعف. في الترتيب بالدلاء، املأ الدلاء بترتيب تصاعدي للقيم، ويكون كل دلو مرتبًا مسبقًا وفق قاعدة كسر التعادل.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def topKFrequent(nums, k):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
المتوقع
[4, 1]