Summary Ranges

Q: ما هو التعقيد الزمني لنطاقات الملخص؟

O(n) . تتم زيارة كل قيمة مرة واحدة، وتُكتب كل فترة مرة واحدة. وباستثناء قائمة المخرجات، تكون المساحة الإضافية O(1) : بداية الفترة الحالية ومؤشر أو مؤشرين.

سهلالفترات المصفوفات والسلاسل النصية

+10

لديك مصفوفة مرتبة nums من أعداد صحيحة متميزة. قسّمها إلى أقل عدد ممكن من النطاقات ذات الأعداد الصحيحة المتتالية، بحيث تنتمي كل قيمة إلى نطاق واحد بالضبط. اكتب النطاق a..b كنص "a->b"، أو "a" عندما يحتوي على قيمة واحدة. أعد النطاقات بترتيب تصاعدي.

الدالة

summaryRanges(nums: integer-array) → string-array

numsinteger-array: المصفوفة المرتبة من الأعداد الصحيحة المتميزة
تُرجعstring-array: النطاقات كنص، من أصغر القيم إلى أكبرها

القيود

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums مرتبة بترتيب تصاعدي ولا تحتوي على عناصر مكررة.

أمثلة

المدخلات: 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.

سؤال إضافي

افترض أن nums قد تحتوي على عناصر مكررة، مثل [1, 2, 2, 3]. ما الذي ستغيّره كي تستمر في طباعة "1->3"؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

بما أن القيم مرتبة ومتميزة، فإن نطاقًا من الأعداد الصحيحة المتتالية يكون دائمًا سلسلة من العناصر المتجاورة في المصفوفة، وينتهي النطاق بالضبط عندما يختلف عنصران متجاوران بأكثر من 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؛ حوّل القيم إلى أعداد صحيحة قبل لصقها.

أسئلة شائعة3

ما هو التعقيد الزمني لنطاقات الملخص؟

O(n). تتم زيارة كل قيمة مرة واحدة، وتُكتب كل فترة مرة واحدة. وباستثناء قائمة المخرجات، تكون المساحة الإضافية O(1): بداية الفترة الحالية ومؤشر أو مؤشرين.

لماذا يؤدي القطع عند كل فجوة إلى أقل عدد من النطاقات؟

يحتوي النطاق على أعداد صحيحة متتالية، لذلك لا يمكن أن يحتوي على قيمتين يفصل بينهما عدد مفقود. لذا يجب أن تفصل كل فجوة في المصفوفة المرتبة بين نطاقين، ومع وجود g فجوات، تحتاج إلى g+1 نطاقات على الأقل. ويؤدي القطع عند الفجوات فقط إلى الحصول على g+1 نطاقات بالضبط.

كيف تتعامل مع نطاق يحتوي على رقم واحد فقط؟

تحقّق مما إذا كان النطاق يبدأ وينتهي بالقيمة نفسها. إذا كان كذلك، فاكتب تلك القيمة وحدها، مثل "9". وإذا لم يكن كذلك، فاكتب قيمة البداية، ثم السهم، ثم قيمة النهاية، مثل "5->6". باستخدام مؤشّرين، يكون الاختبار i == j.

def summaryRanges(nums):
    # اكتب الكود هنا

اختبار #1

اختبار #2

وسيط

nums = [0, 1, 2, 5, 6, 9]

الإخراج المتوقع

["0->2", "5->6", "9"]