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.
سؤال إضافي
افترض أن القيم تصل واحدة تلو الأخرى، وبعد كل قيمة يجب أن تعرض أطول سلسلة متتالية حتى الآن. هل يمكنك إبقاء الإجابة مُحدَّثة بمتوسط زمن 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، إلى أن تغيب إحدى القيم، واحتفظ بأطول عدد. لكل سلسلة متتالية أصغر قيمة في 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.
تستغرق عملية الترتيب 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مجموعة تجزئة، مع العدّ بدءًا من بداية كل تشغيل فقط
الفكرة
مع كل قيمة في مجموعة تجزئة، يستغرق التحقق من العضوية O(1) في المتوسط، وتندمج التكرارات في مدخلة واحدة.
لكن المرور بدءًا من كل قيمة سيكرر العمل: في المتتالية 1, 2, 3, 4 ستخطو 3 خطوات بدءًا من 1، وخطوتين بدءًا من 2، وخطوة واحدة بدءًا من 3. لذا ابدأ المرور فقط من أول قيمة في المتتالية، وهي بالضبط قيمة x التي تكون فيها x-1 غير موجودة. في المثال 1، تنطبق هذه القاعدة على 1 و39 فقط، ما يعطي متتاليتين بطولين 4 و3.
تنتمي كل قيمة إلى متتالية واحدة، ولا يُخطى عليها إلا أثناء المرور الخاص بتلك المتتالية، لذا لا تتجاوز الخطوات في جميع عمليات المرور مجتمعة n خطوة. ومع إجراء تحقق واحد لكل قيمة، يكون الزمن الإجمالي O(n) والذاكرة المطلوبة للمجموعة O(n).
الخوارزمية
- ضع كل قيمة من
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بدلًا من المجموعة. إذا ظهرت القيمة الأولى في متتالية طولها 2,500 عددًا 2,000 مرة، فسيُمرَّر على المتتالية 2,000 مرة. - استخدام القيمة فهرسًا لمصفوفة. تصل القيم إلى
±10^9، لذا ستحتاج إلى2 × 10^9خانة.
أسئلة شائعة3
ما هو التعقيد الزمني لمشكلة أطول تسلسل متتالٍ؟
يعمل حل مجموعة التجزئة بزمن O(n) في المتوسط، مع ذاكرة إضافية O(n). يستغرق الفرز وحساب أطوال التتابعات O(n log n). يستغرق البحث في المصفوفة عن كل قيمة تالية دون استخدام مجموعة ما يصل إلى O(n³).
هل يمكنك حل مسألة أطول تسلسل متتالٍ دون استخدام ذاكرة إضافية؟
نعم، إذا كان بإمكانك إعادة ترتيب المُدخلات: رتّبها في مكانها وعدّ التتابعات في مرور واحد، مع تخطي العناصر المكررة. يتطلب ذلك ذاكرة إضافية O(1)، لكنه يستغرق وقتًا قدره O(n log n). أما الحل ذو التعقيد O(n) فيتطلب مجموعة تجزئة.
هل يمكن لبنية الاتحاد-والبحث حل مسألة أطول تسلسل متتالٍ؟
نعم. اجعل كل قيمة مميزة مجموعة، واربط x بـ x+1 كلما كانتا موجودتين، وأعِد حجم أكبر مجموعة. يعمل بزمن يقارب O(n)، لكنه يحتاج إلى خريطة تربط القيم بالفهرس، وروابط للآباء وأحجامها، بينما لا تحتاج عملية المرور على مجموعة التجزئة إلا إلى مجموعة واحدة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def longestConsecutive(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [40, 4, 39, 1, 3, 2, 41]
الإخراج المتوقع
4