Second Largest Number
لديك قائمة من الأعداد الصحيحة nums. أعد ثاني أكبر قيمة مميزة فيها: أكبر قيمة أصغر تمامًا من القيمة العظمى. يمكن أن تتكرر القيم، لذا تكون الإجابة 3 للقائمة [5, 5, 3]، وليس 5. تحتوي القائمة دائمًا على قيمتين مختلفتين على الأقل.
الدالة
- numsinteger-array
- قائمة الأعداد الصحيحة، التي تحتوي على قيمتين مختلفتين على الأقل
- تُرجعinteger
- أكبر قيمة أصغر من الحد الأقصى
القيود
2 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsيحتوي على قيمتين مختلفتين على الأقل.
أمثلة
- المدخلات
- nums = [4, 9, 2, 7, 9]
- المخرجات
- 7
- الشرح
- القيمة القصوى هي
9. تظهر مرتين، لكن النسخة الثانية من القيمة القصوى لا تُحتسب، لذا فالإجابة هي القيمة التالية الأقل،7.
- المدخلات
- nums = [-5, -1, -8]
- المخرجات
- -5
- الشرح
- من الأكبر إلى الأصغر، القيم هي
-1و-5و-8. ثاني أكبر قيمة هي-5، رغم أنها سالبة.
- المدخلات
- nums = [6, 6, 6, 3]
- المخرجات
- 3
- الشرح
- توجد قيمتان مختلفتان فقط،
6و3. مهما تكرر6من مرات، فإن ثاني أكبر قيمة هي3.
سؤال إضافي
هل يمكنك إرجاع ثالث أكبر قيمة مميزة في مرور واحد، باستخدام ثلاثة متغيرات ومن دون فرز؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
يتطلب إيجاد القيمة القصوى متغيرًا واحدًا. ما الذي سيسمح لك متغير ثانٍ بتذكّره أثناء قراءة القائمة؟
تتبّع أكبر قيمة وثاني أكبر قيمة مختلفتين. يمكن لقيمة جديدة أن تتجاوز الأكبر، أو تقع بين القيمتين بشكل صارم، أو لا تغيّر شيئًا.
ابدأ كلا المتغيرين أدناه بأي قيمة مسموح بها. إذا كان
x > largest، فانقلlargestإلىsecondوخزّنx. وإلا، إذا كانت قيمةxتقع بينهما حصريًا، فخزّنها فيsecond.
الحل
هناك تفصيلان يجعلان هذا أصعب من إيجاد القيمة القصوى. قد تتكرر القيمة القصوى، ويجب ألا يُبلّغ عن قيمة مكررة على أنها ثاني أكبر قيمة. قد تكون الإجابة سالبة، لذا فإن متغيرًا يبدأ عند 0 يعطي إجابة خاطئة لقائمة تتكون من قيم سالبة فقط. إن تتبّع أكبر قيمتين مختلفتين في مرور واحد، باستخدام مقارنات صارمة، يعالج الأمرين.
رتّب وتجاوز الحد الأقصى
الفكرة
رتّب نسخة تصاعديًا من الأصغر إلى الأكبر. تكون القيمة العظمى في النهاية، وقد تتكرر عدة مرات متتالية. تحرّك إلى اليسار من النهاية متجاوزًا كل تكرارات القيمة العظمى؛ أول قيمة مختلفة هي ثاني أكبر قيمة. في [6, 6, 6, 3] تكون النسخة المرتّبة [3, 6, 6, 6]: تتجاوز ثلاث قيم 6 وتصل إلى 3.
إرجاع العنصر ما قبل الأخير هو الخطأ الشائع هنا. ففي [4, 9, 2, 7, 9] سيُرجع 9، أي القيمة العظمى مرة أخرى. لا يمكن أن تتجاوز الحركة بداية القائمة، لأن القائمة تحتوي على قيمتين مختلفتين على الأقل.
الإجابة صحيحة، لكن الترتيب يرتب كل القيم بينما لا يهمك سوى أكبر قيمتين. تكلفته الزمنية O(n log n) وتستهلك النسخة O(n) من الذاكرة.
الخوارزمية
- انسخ
numsورتّب النسخة تصاعديًا من الأصغر إلى الأكبر. - ابدأ الفهرس
iعند الموضع الأخير. - ما دامت القيمة عند
iتساوي القيمة القصوى، حرّكiخطوة واحدة إلى اليسار. - أعِد القيمة عند
i.
def secondLargest(nums):
ordered = sorted(nums)
i = len(ordered) - 1
# Step left past every copy of the maximum.
while ordered[i] == ordered[-1]:
i -= 1
return ordered[i]تمريرتان
الفكرة
قسّم المهمة إلى مرحلتين. تعثر المرحلة الأولى على القيمة العظمى، كما في «العثور على أكبر عدد». وتبحث المرحلة الثانية عن أكبر قيمة أصغر من تلك القيمة العظمى بشكل صارم. في [4, 9, 2, 7, 9] تعثر المرحلة الأولى على 9، وتتجاوز المرحلة الثانية كلا القيمتين 9 وتحتفظ بأكبر قيمة من 4 و2 و7، وهي 7.
ابدأ second بقيمة أقل من كل القيم التي يمكن أن تحتويها القائمة، مثل أصغر عدد صحيح تدعمه لغتك. تحتوي القائمة على قيمتين مختلفتين على الأقل، لذا توجد قيمة أصغر من القيمة العظمى وستحل دائمًا محل قيمة البداية تلك.
كل مرحلة تحسب قيمة عظمى متتابعة، لذا يكون الإجمالي O(n) من حيث الزمن وO(1) من حيث المساحة. وتكمن الكلفة في قراءة القائمة مرتين، وهذا مستحيل عندما تصل القيم واحدة تلو الأخرى وتختفي بعد قراءتها.
الخوارزمية
- تكرّر على
numsمرة واحدة وخزّن القيمة القصوى فيlargest. - اضبط
secondعلى قيمة أقل من كل قيمة مسموح بها. - كرّر مرة أخرى. لكل
xبحيثx < largestوx > second، اضبطsecondعلىx. - أعِد
second.
def secondLargest(nums):
largest = nums[0]
for x in nums:
if x > largest:
largest = x
second = float("-inf") # below every allowed value
for x in nums:
if x < largest and x > second:
second = x
return secondتمرير واحد لتتبّع أكبر قيمتين
الفكرة
احتفظ بمتغيرين، largest وsecond، لأكبر قيمتين مختلفتين ظهرتا حتى الآن. تقع كل قيمة جديدة x ضمن واحدة من ثلاث حالات. إذا كانت x أكبر من largest، تنتقل قيمة largest القديمة إلى المرتبة الثانية، وتتولى x المرتبة الأولى. إذا كانت x تقع strictly بين second وlargest، فتصبح قيمة second الجديدة. في كل حالة أخرى، لا يتغير شيء.
المقارنات الصارمة هي ما يعالج القيم المكررة. بالنسبة إلى [4, 9, 2, 7, 9]: تصبح قيمة largest هي 4، ثم 9 مع second = 4. لا تغيّر 2 شيئًا، وتقع 7 بين 4 و9، لذا تصبح second = 7، أما 9 الأخيرة فتساوي largest، لذا يتم تخطيها. الإجابة هي 7.
ابدأ بكلا المتغيرين بقيمتين أقل من كل قيمة ممكنة. بدء كليهما عند 0 يعيد 0 للقائمة [-5, -1, -8]، لأنه لا توجد أي قيمة تتجاوز 0. وبما أن القائمة تحتوي على قيمتين مختلفتين، فإن second تنتهي دائمًا بقيمة فعلية من القائمة.
الخوارزمية
- عيّن
largestوsecondإلى قيمتين أقل من كل القيم المسموح بها. - كرّر على كل قيمة
xفيnums. - إذا كان
x > largest، فانقلlargestإلىsecondوعيّنlargestإلىx. - وإلا، إذا كان
x < largestوx > second، فعيّنsecondإلىx. - بعد انتهاء الحلقة، أعد
second.
def secondLargest(nums):
# Both start below every allowed value.
largest = second = float("-inf")
for x in nums:
if x > largest:
second = largest # the old maximum drops to second place
largest = x
elif largest > x > second:
second = x
return second
أخطاء شائعة وحالات حدّية
تأتي معظم الإجابات الخاطئة من تكرار القيمة العظمى أو من القيم السالبة.
- إرجاع العنصر قبل الأخير من القائمة المرتبة. عند تكرار القيمة العظمى، كما في
[4, 9, 2, 7, 9]، يكون هذا العنصر هو القيمة العظمى مجددًا. - بدء المتغيرات بالقيمة
0. في[-5, -1, -8]، لا تتجاوز أي قيمة0، فتُرجع0، وهو عدد غير موجود في القائمة. - كتابة
x >= largestفي الحالة الأولى. عندئذٍ، تدفع قيمة9ثانية قيمة9الأولى إلىsecond، فتُرجع9. - تحديث
secondفقط عند ظهور قيمة عظمى جديدة. في[10, 20, 15]، لا تصل قيمة15أبدًا إلىsecond، فتُرجع10. - إزالة القيم المكررة باستخدام مجموعة ثم الترتيب. تنجح هذه الطريقة، لكنها تستهلك ذاكرة بمقدار
O(n)ووقتًا بمقدارO(n log n)لمهمة تنجزها عملية مرور واحدة.
أسئلة شائعة3
كيف تجد ثاني أكبر عدد في مصفوفة في مرور واحد؟
احتفِظ بأكبر قيمة وأكبر قيمة ثانية متميزة رأيتهما حتى الآن. عندما تتجاوز قيمةٌ القيمةَ الأكبر، تنتقل القيمة الأكبر السابقة إلى المرتبة الثانية. وعندما تقع قيمة بين القيمتين دون أن تساوي أيًّا منهما، فإنها تحل محل القيمة الثانية. بعد مرور واحد، يحتوي المتغير الثاني على الإجابة.
ما هو التعقيد الزمني لإيجاد ثاني أكبر عنصر؟
تستغرق طريقتا المرور الواحد والمرورين كلتاهما وقتًا قدره O(n) ومساحة إضافية قدرها O(1). أما الفرز أولًا فيستغرق وقتًا قدره O(n log n). لا يمكنك تحقيق أداء أفضل من O(n)، لأن كل قيمة يجب قراءتها مرة واحدة على الأقل.
كيف تؤثر القيم المكررة في العنصر الثاني الأكبر؟
تطلب هذه المسألة إيجاد ثاني أكبر قيمة مميزة، لذا يتم تجاهل النسخ المكررة من القيمة العظمى. بالنسبة إلى [9, 9, 7]، الإجابة هي 7. بعض صيغ السؤال تحتسب المواضع بدلًا من ذلك، وستكون الإجابة عندئذٍ 9، لذا تحقّق مما هو المقصود قبل كتابة الكود.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def secondLargest(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [4, 9, 2, 7, 9]
الإخراج المتوقع
7