Summary Ranges
لديك مصفوفة مرتبة nums من أعداد صحيحة متميزة. قسّمها إلى أقل عدد ممكن من النطاقات ذات الأعداد الصحيحة المتتالية، بحيث تنتمي كل قيمة إلى نطاق واحد بالضبط. اكتب النطاق a..b كنص "a->b"، أو "a" عندما يحتوي على قيمة واحدة. أعد النطاقات بترتيب تصاعدي.
الدالة
- numsinteger-array
- المصفوفة المرتبة من الأعداد الصحيحة المتميزة
- تُرجعstring-array
- النطاقات كنص، من أصغر القيم إلى أكبرها
القيود
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsمرتبة بترتيب تصاعدي ولا تحتوي على عناصر مكررة.
أمثلة
- المدخلات
- nums = [0, 1, 2, 5, 6, 9]
- المخرجات
- ["0->2", "5->6", "9"]
- الشرح
- تأتي
0, 1, 2متتالية، لذا تشكّل"0->2". تقفز الأعداد من 2 إلى 5، فتبدأ نطاقًا جديدًا هو"5->6"، ويبقى 9 منفردًا على هيئة"9".
- المدخلات
- nums = [-3, -1, 0, 1, 4, 7, 8]
- المخرجات
- ["-3", "-1->1", "4", "7->8"]
- الشرح
- لا يوجد لـ -3 جار (-2 مفقود)، وتشكل
-1, 0, 1سلسلة متتابعة، بينما يبقى 4 منفردًا، وتُختتم القائمة بـ7, 8. تعمل القيم السالبة بالطريقة نفسها: يتبع -1 العدد -1 + 1 = 0.
+16 اختبارات مخفية عند الإرسال
سؤال إضافي
افترض أن nums قد تحتوي على عناصر مكررة، مثل [1, 2, 2, 3]. ما الذي ستغيّره كي تستمر في طباعة "1->3"؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
المصفوفة مرتبة. متى تنتمي قيمتان متجاورتان إلى النطاق نفسه؟
ينتميان إلى النطاق نفسه بالضبط عندما يكون
nums[i+1] == nums[i] + 1. وكل زوج آخر من العناصر المتجاورة يحدّد نهاية نطاق وبداية النطاق التالي.تذكّر أين بدأ النطاق الحالي. تقدّم ما دام العنصر التالي يزيد بمقدار واحد عن العنصر الحالي؛ وعندما ينقطع التتابع أو تصل إلى نهاية المصفوفة، اكتب النطاق من بدايته إلى العنصر الحالي، وابدأ النطاق التالي من العنصر الذي يليه.
الحل
تحقّق من الجارين لكل قيمة
الفكرة
انظر إلى قيمة واحدة في كل مرة واطرح سؤالين. هل يبدأ نطاق هنا؟ نعم، عندما تكون هذه أول قيمة أو عندما لا تكون القيمة السابقة أقل منها بواحد. هل ينتهي نطاق هنا؟ نعم، عندما تكون هذه آخر قيمة أو عندما لا تكون القيمة التالية أكبر منها بواحد.
في [0, 1, 2, 5, 6, 9]، يبدأ نطاق عند 0 و5 و9، وينتهي عند 2 و6 و9. تذكّر القيمة التي بدأ عندها النطاق الحالي. عندما ينتهي نطاق عند nums[i]، اكتب "start->nums[i]"، أو "start" فقط عندما يبدأ النطاق وينتهي عند القيمة نفسها، كما يحدث مع 9.
تتم زيارة كل قيمة مرة واحدة، مع النظر إلى جارَين لها، لذا يكون الزمن O(n). وباستثناء الناتج، تحتفظ ببداية واحدة متذكَّرة، لذا تكون المساحة الإضافية O(1).
الخوارزمية
- عيّن
start = nums[0]. - لكل فهرس
i: إذا كانi > 0وnums[i] != nums[i-1] + 1، فعيّنstart = nums[i]. - إذا كان
iهو الفهرس الأخير أو كانnums[i+1] != nums[i] + 1، ينتهي النطاق هنا. - أضف
"start"عندما يكونstart == nums[i]، وإلا فأضف"start->nums[i]". - أعِد القائمة بعد الفهرس الأخير.
def summaryRanges(nums):
n = len(nums)
ranges = []
start = nums[0]
for i in range(n):
# A range opens where the value before is not one less.
if i > 0 and nums[i] != nums[i - 1] + 1:
start = nums[i]
# A range closes where the value after is not one more.
if i == n - 1 or nums[i + 1] != nums[i] + 1:
ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
return rangesمؤشران على كل تتابع
الفكرة
تعامل مع كل نطاق على أنه كتلة من المصفوفة، وحدد طرفيه. يقف المؤشر i عند القيمة الأولى في النطاق. يبدأ المؤشر j عند i ويتحرك إلى اليمين ما دامت القيمة التالية تزيد بمقدار واحد بالضبط، لذا يتوقف عند القيمة الأخيرة في النطاق.
بالنسبة إلى [-3, -1, 0, 1, 4, 7, 8]: لا يمكن لـ i عند -3 التمدد، لأن -1 ليس -2، لذا يكون النطاق "-3". ثم ينتقل i إلى -1، ويتحرك j عبر 0 و1 ويتوقف قبل 4: "-1->1". ثم "4" و"7->8". بعد كل نطاق، ينتقل i إلى j+1، وهي القيمة الأولى في النطاق التالي.
عدد النطاقات هو الأقل الممكن: لا يمكن لقيمتين يفصل بينهما فجوة أن تنتميا إلى النطاق نفسه، والطريقة لا تقسّم إلا عند الفجوات. يتحرك المؤشران إلى الأمام فقط، لذا تُنفَّذ الحلقة الداخلية n مرة إجمالًا عبر جميع النطاقات، ما يحافظ على الزمن عند O(n) والمساحة الإضافية عند O(1).
الخوارزمية
- عيّن
i = 0. - عيّن
j = i، وحرّكjإلى اليمين ما دامj+1 < nوnums[j+1] == nums[j] + 1. - أضف
"nums[i]"عندما يكونi == j، وإلا فأضف"nums[i]->nums[j]". - عيّن
i = j + 1وكرّر إلى أن يتجاوزiالنهاية. - أعِد القائمة.
def summaryRanges(nums):
ranges = []
n = len(nums)
i = 0
while i < n:
# i is the first value of a run; push j to its last value.
j = i
while j + 1 < n and nums[j + 1] == nums[j] + 1:
j += 1
ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
# The next run starts right after this one.
i = j + 1
return ranges
أخطاء شائعة وحالات حدّية
المنطق لا يحتاج إلا إلى بضعة أسطر؛ أما الأخطاء فتحدث عند الأطراف.
- نسيان النطاق الأخير. الحلقة التي تكتب نطاقًا فقط عندما تصادف فجوة لا تكتب النطاق الأخير أبدًا، لذا تفقد
[0, 1, 2, 5, 6, 9]القيمة"9". أغلق نطاقًا عند الفهرس الأخير أيضًا. - كتابة
"a->a"لقيمة واحدة. يُكتب النطاق الذي يحتوي على قيمة واحدة بصيغة"a". - طباعة القيم الكبيرة بالتدوين العلمي. يحوّل R قيمة double مثل
1000000000إلى1e+09؛ حوّل القيم إلى أعداد صحيحة قبل لصقها.
أسئلة شائعة4
ما هو التعقيد الزمني لنطاقات الملخص؟
O(n). تتم زيارة كل قيمة مرة واحدة، وتُكتب كل فترة مرة واحدة. وباستثناء قائمة المخرجات، تكون المساحة الإضافية O(1): بداية الفترة الحالية ومؤشر أو مؤشرين.
لماذا يؤدي القطع عند كل فجوة إلى أقل عدد من النطاقات؟
يحتوي النطاق على أعداد صحيحة متتالية، لذلك لا يمكن أن يحتوي على قيمتين يفصل بينهما عدد مفقود. لذا يجب أن تفصل كل فجوة في المصفوفة المرتبة بين نطاقين، ومع وجود g فجوات، تحتاج إلى g+1 نطاقات على الأقل. ويؤدي القطع عند الفجوات فقط إلى الحصول على g+1 نطاقات بالضبط.
كيف تتعامل مع نطاق يحتوي على رقم واحد فقط؟
تحقّق مما إذا كان النطاق يبدأ وينتهي بالقيمة نفسها. إذا كان كذلك، فاكتب تلك القيمة وحدها، مثل "9". وإذا لم يكن كذلك، فاكتب قيمة البداية، ثم السهم، ثم قيمة النهاية، مثل "5->6". باستخدام مؤشّرين، يكون الاختبار i == j.
هل تحتاج نطاقات الملخص إلى أن تكون المدخلات مرتبة؟
نعم. تقارن الطريقة بين العناصر المتجاورة فقط، لذا فهي تعتمد على وجود الأعداد الصحيحة المتتالية بجانب بعضها. إذا كانت المدخلات غير مرتبة، فرتّبها أولًا، وهذا يجعل المهمة بأكملها O(n log n)، أو ضع القيم في مجموعة تجزئة ووسّع كل نطاق بدءًا من أصغر قيمة فيه، كما في مسألة أطول تسلسل متتالٍ.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def summaryRanges(nums):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
nums = [0, 1, 2, 5, 6, 9]
المتوقع
["0->2", "5->6", "9"]