Longest Consecutive Sequence
تحصل على مصفوفة من الأعداد الصحيحة nums بترتيب غير محدد. التسلسل المتتابع هو مجموعة من القيم x وx+1 وx+2 وهكذا، تظهر كل منها في موضع ما ضمن nums. أعد طول أطول تسلسل متتابع. تُحتسب القيمة التي تظهر أكثر من مرة مرة واحدة.
الدالة
- numsinteger-array
- الأعداد الصحيحة، بأي ترتيب، مع السماح بالتكرار
- تُرجعinteger
- طول أطول سلسلة من القيم المتتالية الموجودة في nums
القيود
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- قد تتكرر القيم. لا تهم المواضع في المصفوفة، بل المهم فقط القيم الموجودة.
أمثلة
- المدخلات
- nums = [40, 4, 39, 1, 3, 2, 41]
- المخرجات
- 4
- الشرح
- القيم
1و2و3و4كلها موجودة، وهي سلسلة من 4 قيم، رغم أنها متفرقة في المصفوفة. أما السلسلة الأخرى، من39إلى41، فتضم 3 قيم فقط.
- المدخلات
- nums = [7, 3, 7, 5, 6, 5]
- المخرجات
- 3
- الشرح
5و6و7تشكّل سلسلة من 3 أعداد. لا يضيف العدد7الثاني ولا العدد5الثاني شيئًا، ولا يمكن أن ينضم3لأن4مفقود.
- المدخلات
- nums = [10, 30, 20]
- المخرجات
- 1
- الشرح
- لا تختلف أي قيمتين بمقدار 1، لذا تحتوي كل سلسلة متتالية على قيمة واحدة، والإجابة هي 1.
+17 اختبارات مخفية عند الإرسال
سؤال إضافي
افترض أن القيم تصل واحدة تلو الأخرى، وأنه عليك بعد كل قيمة الإبلاغ عن أطول سلسلة متتالية حتى الآن. هل يمكنك إبقاء الإجابة محدّثة في زمن متوسط O(1) لكل قيمة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
جرّب كل قيمة باعتبارها الرقم الأول في متتالية، ثم عُدّ تصاعديًا. ما السؤال الذي تكرّره مرارًا، وما تكلفة كل إجابة عندما تبحث عنها في المصفوفة؟
السؤال هو «هل
x+1موجود في المصفوفة؟». وتجيب مجموعة التجزئة عن ذلك في زمن ثابت في المتوسط، كما أنها تزيل العناصر المكررة.ابدأ العدّ فقط عند قيمة
xالتي تكونx-1غير موجودة في المجموعة. ومن هناك، انتقل إلىx+1، ثمx+2، وتابع ما دامت المجموعة تحتوي عليها، واحتفظ بأطول مسار. وهكذا لا يمرّ أيّ عنصر إلا ضمن مسار واحد.
الحل
يمكن أن تكون قيم المتتالية في أي موضع داخل المصفوفة، لذا لا يمكنك قراءة المتتاليات من اليسار إلى اليمين. يرتّبها الفرز لتصبح متتابعة في O(n log n). وتؤدي مجموعة التجزئة أداءً أفضل: فهي تجيب عن السؤال «هل x+1 موجود هنا؟» في O(1)، وإذا بدأت العدّ فقط من القيم التي لا توجد فيها x-1، فسيتم تجاوز كل قيمة مرة واحدة، ما يجعل البحث بأكمله O(n).
العد تصاعديًا بدءًا من كل قيمة من خلال البحث في المصفوفة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اعتبر كل قيمة بداية محتملة لمتتالية. انطلاقًا من x، ابحث في المصفوفة عن x+1؛ وإذا كانت موجودة، فابحث عن x+2، وواصل البحث حتى تجد قيمة مفقودة. عدد القيم التي وصلت إليها هو طول المتتالية التي تبدأ عند x، وأكبر هذه الأطوال هو الإجابة.
هذا صحيح لأن لكل متتالية قيمة صغرى، وهذه القيمة موجودة في nums، والحلقة تجرّبها كبداية وتسير عبر المتتالية بأكملها. التكرارات لا تسبب أي مشكلة: فهي تجعلنا نجرّب البداية نفسها مرتين فقط.
هذه الطريقة بطيئة لسببين. فكل عملية «هل هي موجودة هنا؟» تقرأ ما يصل إلى n قيمة، كما يُعاد اجتياز المتتالية الطويلة بدءًا من كل عنصر فيها. لنأخذ 10^4 قيمة تكوّن متتالية واحدة بترتيب عشوائي: يصل مجموع خطوات الاجتياز إلى نحو n²/2 = 5 × 10^7 خطوة، ويفحص كلٌّ منها، في المتوسط، نصف عناصر المصفوفة. أي نحو 2.5 × 10^11 مقارنة.
الخوارزمية
- عيّن
bestإلى 0. - لكل قيمة
startفيnums، عيّنcurrentإلىstartوlengthإلى 1. - ما دام مسح
numsيعثر علىcurrent+1، أضف 1 إلىcurrentوإلىlength. - خزّن
lengthفيbestإذا كانت أكبر. - أعِد
best.
def longestConsecutive(nums):
best = 0
for start in nums:
current = start
length = 1
# "in" on a list reads it from the front until it finds the value.
while current + 1 in nums:
current += 1
length += 1
best = max(best, length)
return bestرتّب، ثم احسب التتابعات
الفكرة
يرتّب الفرز قيم كل سلسلة متتالية بجانب بعضها. تصبح [40, 4, 39, 1, 3, 2, 41] بالشكل [1, 2, 3, 4, 39, 40, 41]، وتُقرأ السلاسل من اليسار إلى اليمين: من 1 إلى 4، ثم قفزة إلى 39.
مرّ على القيم المرتبة واحتفظ بطول السلسلة المتتالية الحالية. القيمة التي تزيد بمقدار واحد عن السابقة تمدّدها. أما القيمة المساوية للسابقة فهي تكرار: تخطّها، لأنها لا تمدّد السلسلة ولا تنهيها. وأي قيمة أخرى تمثّل فجوة، وتبدأ عندها سلسلة جديدة بطول 1.
تبلغ كلفة الفرز O(n log n)، وكلفة المرور O(n). لا يتطلب الفرز في المكان مصفوفة إضافية، لكنه يعيد ترتيب مدخلات المستدعي؛ أما اللغات التي تفرز نسخة فتستخدم ذاكرة بمقدار O(n).
الخوارزمية
- رتّب
numsترتيبًا تصاعديًا. - عيّن
bestوrunإلى 1، لأن المصفوفة لا تكون فارغة أبدًا. - لكل فهرس
iبدءًا من 1، تخطَّnums[i]إذا كان يساويnums[i-1]. - إذا كانت قيمة
nums[i]تساويnums[i-1]+1، فأضف 1 إلىrun؛ وإلا فعيّنrunإلى 1. خزّنrunفيbestإذا كانت قيمته أكبر. - أعِد
best.
def longestConsecutive(nums):
nums.sort()
best = 1
run = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue # a repeat neither extends nor breaks the run
if nums[i] == nums[i - 1] + 1:
run += 1
else:
run = 1
best = max(best, run)
return bestمجموعة تجزئة، مع العدّ بدءًا من بداية كل تشغيل فقط
الفكرة
ضع كل قيمة في مجموعة تجزئة. عندها، يصبح الاستعلام «هل x+1 موجود؟» بتكلفة O(1) في المتوسط بدلًا من البحث، وتندمج القيم المكررة في إدخال واحد.
البدء من كل قيمة سيؤدي مع ذلك إلى تكرار العمل: في التسلسل 1, 2, 3, 4 ستخطو 3 خطوات انطلاقًا من 1، وخطوتين من 2، وخطوة واحدة من 3. لذا ابدأ السير فقط عند القيمة الأولى في التسلسل. تكون القيمة x هي الأولى بالضبط عندما لا تكون x-1 في المجموعة. في [40, 4, 39, 1, 3, 2, 41] لا ينطبق ذلك إلا على 1 و39: من 1 تصل إلى 4، بطول 4، ومن 39 تصل إلى 41، بطول 3.
تنتمي كل قيمة إلى تسلسل واحد بالضبط، ولا يمرّ عليها إلا السير الذي يبدأ من القيمة الأولى في ذلك التسلسل، لذا تستغرق جميع عمليات السير مجتمعةً ما لا يزيد على n خطوة. أضف فحص عضوية واحدًا لكل قيمة وبناء المجموعة، فيكون الإجمالي O(n) من الزمن، مع استخدام O(n) من الذاكرة للمجموعة.
كرّر المرور على المجموعة، لا على nums. إذا ظهرت القيمة الأولى في تسلسل مكوّن من 2,500 قيمة 2,000 مرة في nums، فإن المرور على nums سيجتاز ذلك التسلسل 2,000 مرة.
الخوارزمية
- ضع كل قيمة من
numsفي مجموعة تجزئةvalues، واضبطbestعلى 0. - لكل قيمة
xفي المجموعة، تخطَّها إذا كانتx-1موجودة في المجموعة: فهي ليست القيمة الأولى في تسلسلها. - وإلا، فاضبط
endعلىxوأضف إليه 1 ما دامend+1موجودًا في المجموعة. - خزّن
end-x+1فيbestإذا كانت أكبر قيمة. - أعِد
best.
def longestConsecutive(nums):
values = set(nums)
best = 0
for value in values:
# Only a value with no left neighbour starts a run.
if value - 1 in values:
continue
end = value
while end + 1 in values:
end += 1
best = max(best, end - value + 1)
return best
أخطاء شائعة وحالات حدّية
تأتي معظم الإجابات الخاطئة من القيم المتكررة، وتأتي معظم الإجابات البطيئة من اجتياز التسلسل نفسه أكثر من مرة.
- اعتبار التكرار فجوة أو خطوة بعد الترتيب. في
[1, 2, 2, 3]، يؤدي إعادة ضبط التسلسل عند الرقم2الثاني إلى إعطاء 2، واحتسابه خطوةً يعطي 4. الإجابة هي 3. - بدء
bestبالقيمة 0 أثناء الاجتياز المرتب وتحديثه داخل الحلقة فقط. عندها تُرجع مصفوفة تحتوي على قيمة واحدة 0 بدلًا من 1. - الاجتياز بدءًا من كل قيمة في المجموعة بدلًا من بدايات التسلسلات فقط. الإجابة صحيحة، لكن تسلسلًا واحدًا من
10^4قيمة يتطلب5 × 10^7خطوة، وهو العمل التربيعي الذي كان الهدف من استخدام المجموعة التخلص منه. - التكرار على
numsبدلًا من المجموعة عند تكرار القيم. يُجتاز التسلسل الذي يبدأ بقيمة تظهر آلاف المرات آلاف المرات. - تعليم القيم في مصفوفة مفهرسة بالقيمة. تصل القيم إلى
±10^9، لذا ستحتاج المصفوفة إلى2 × 10^9مدخلًا.
أسئلة شائعة4
ما هو التعقيد الزمني لتسلسل الأطوال المتتالية؟
يعمل حل مجموعة التجزئة في زمن O(n) في المتوسط، ويستخدم ذاكرة إضافية بمقدار O(n). يستغرق الفرز ثم عدّ المتتاليات زمنًا قدره O(n log n). ويستغرق البحث في المصفوفة عن كل قيمة تالية من دون مجموعة زمنًا يصل إلى O(n³).
لماذا يكون حل مجموعة التجزئة ذا تعقيد O(n) رغم وجود حلقة while داخل حلقة for؟
لا تعمل الحلقة الداخلية إلا بدءًا من قيمة يكون جارها الأيسر x-1 مفقودًا، وهي أول قيمة في تسلسلها. وتتجاوز عملية المرور الخاصة بتسلسل كل قيمة تلك القيمة، ولا تتجاوزها أي عملية مرور أخرى، لذا لا تستغرق الحلقات الداخلية مجتمعةً أكثر من n خطوة. وتضيف الحلقة الخارجية فحصًا واحدًا لكل قيمة، ليكون الإجمالي O(n).
هل يمكنك حل مسألة أطول تسلسل متتالٍ دون ذاكرة إضافية؟
نعم، إذا كان بإمكانك إعادة ترتيب المُدخل: رتّبه في مكانه وعدّ التتابعات في مرور واحد، مع تخطي التكرارات. يستخدم ذلك ذاكرة إضافية O(1)، لكن يستغرق وقتًا O(n log n). أما الحل O(n) فيحتاج إلى مجموعة تجزئة.
هل تستطيع بنية الاتحاد والبحث حل مسألة أطول تسلسل متتالٍ؟
نعم. اجعل كل قيمة مميزة مجموعةً، واربط x بـ x+1 كلما كان كلاهما موجودًا، وأعِد حجم أكبر مجموعة. يعمل هذا في وقت يقارب O(n)، لكنه يحتاج إلى خريطة تربط القيم بالفهرس، وروابط للآباء وأحجامها، بينما تنجز عملية المرور على مجموعة التجزئة المهمة نفسها باستخدام مجموعة واحدة وحلقتين.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def longestConsecutive(nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [40, 4, 39, 1, 3, 2, 41]
المتوقع
4