Running Sum of an Array
لديك مصفوفة من الأعداد الصحيحة nums. أعد مصفوفة جديدة بالطول نفسه، يكون عنصرها عند الفهرس i هو nums[0] + nums[1] + ... + nums[i]، أي مجموع أول i+1 عددًا.
الدالة
- numsinteger-array
- الأعداد المراد جمعها من اليسار إلى اليمين
- تُرجعinteger-array
- المجاميع التراكمية، واحد لكل عنصر من عناصر nums
القيود
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104- كل مجموع تراكمي يلائم عددًا صحيحًا موقّعًا من 32 بت.
أمثلة
- المدخلات
- nums = [3, 1, 4, 1, 5]
- المخرجات
- [3, 4, 8, 9, 14]
- الشرح
- واصل الجمع:
3، ثم3 + 1 = 4، و4 + 4 = 8، و8 + 1 = 9، و9 + 5 = 14. يُضاف كل مجموع إلى فهرس العدد الذي أُضيف أخيرًا.
- المدخلات
- nums = [-2, 5, -3]
- المخرجات
- [-2, 3, 0]
- الشرح
- الأعداد السالبة تُخفّض المجموع:
-2، ثم-2 + 5 = 3، ثم3 + (-3) = 0.
- المدخلات
- nums = [7]
- المخرجات
- [7]
- الشرح
- للعدد الواحد مجموع جارٍ واحد، وهو العدد نفسه، لذا تكون الإجابة
[7].
سؤال إضافي
هل يمكنك إنشاء الشيء نفسه لشبكة، بحيث تحتوي كل خلية على مجموع المستطيل الممتد من الزاوية العلوية اليسرى إلى تلك الخلية؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ما العلاقة بين الإجابة عند الفهرس
iوالإجابة عند الفهرسi-1؟يختلف المجموعان بمقدار عدد واحد بالضبط، وهو
nums[i]. لا تحتاج أبدًا إلى جمع بادئة من البداية مرة أخرى.احتفِظ بمتغير واحد هو
total. مرّ علىnumsمن اليسار إلى اليمين، وأضِف كل رقم إلىtotal، واكتبtotalفي الإجابة عند الفهرس نفسه.
الحل
كل إجابة هي مجموع بادئة من nums، وتختلف البادئات المتجاورة بعنصر واحد. إعادة حساب كل بادئة من البداية تكرر معظم العمل. بدلًا من ذلك، انقل مجموعًا واحدًا إلى الأمام، فتكلفة كل إجابة عملية جمع واحدة.
اجمع كل بادئة من البداية
الفكرة
اتبع التعريف: لكل فهرس i، ابدأ بمجموع قيمته 0، وأضف nums[0] حتى nums[i]، ثم خزّنه. هذا صحيح لأن كل إجابة تُحسب تمامًا كما هو محدد.
يتطلب الفهرس i إجراء i+1 عملية جمع، لذا يتطلب المصفوفة n(n+1)/2 عملية جمع: حوالي 1.25 × 10^7 عملية جمع عندما تكون n = 5000، وهو عدد مناسب.
الخوارزمية
- أنشئ مصفوفة للإجابة بطول
n. - لكل فهرس
i، عيّنtotal = 0. - أضف
nums[j]إلىtotalلكلjمن0إلىi. - خزّن
totalعند الفهرسiفي مصفوفة الإجابة، وأعِد الإجابة بعد الفهرس الأخير.
def runningSum(nums):
result = []
for i in range(len(nums)):
total = 0
for j in range(i + 1):
total += nums[j]
result.append(total)
return resultاحتفِظ بإجماليٍّ جارٍ
الفكرة
مجموع أول i+1 أعداد يساوي مجموع أول i عددًا مضافًا إليه nums[i]: result[i] = result[i-1] + nums[i]. لذلك لن تحتاج أبدًا إلى الرجوع أكثر من خطوة واحدة، ويكفي متغير واحد هو total. بالنسبة إلى [3, 1, 4, 1, 5]، تكون القيم 3، ثم 4، ثم 8، ثم 9، ثم 14، وهي الإجابة.
تتطلب كل قيمة عملية جمع واحدة: زمن O(n) ومساحة إضافية O(1) إلى جانب الإجابة.
الخوارزمية
- أنشئ مصفوفة للإجابة بطول
nواجعلtotal = 0. - مرّ على الفهارس من اليسار إلى اليمين وأضف
nums[i]إلىtotal. - اكتب
totalفي الفهرسiمن مصفوفة الإجابة. - أعِد الإجابة.
def runningSum(nums):
result = []
total = 0
for num in nums:
total += num
result.append(total)
return result
أخطاء شائعة وحالات حدّية
- إعادة ضبط
totalداخل الحلقة. تصبح كل إجابة هيnums[i]وحدها، وتُعاد[3, 1, 4]دون تغيير. - قراءة
result[i-1]عندi = 0. تتجاوز معظم اللغات حدود المصفوفة؛ أما Python فتقرأ العنصر الأخير، لذا فإن النسخة التي تعدّل المصفوفة في مكانها تضيف العدد الأخير إلى الأول. - إيقاف الحلقة الداخلية لطريقة القوة الغاشمة عند
j < i. يؤدي ذلك إلى استبعادnums[i]، لذا تكون كل إجابة ناقصة بمقدار عدد واحد. - في R، تؤدي زيادة الإجابة باستخدام
result <- c(result, total)إلى نسخ المتجه في كل خطوة، مما يجعل الطريقة السريعة تربيعية التعقيد. خصّص الطول الكامل أولًا. - في C، نسيان
*returnSize = numsSize. عندئذٍ لن يعرف المستدعي عدد المجاميع التي عليه قراءتها.
أسئلة شائعة4
ما هو المجموع التراكمي لمصفوفة؟
إنها مصفوفة ثانية يكون كل عنصر فيها مجموع جميع العناصر حتى الموضع نفسه في المصفوفة الأولى، شاملًا ذلك الموضع. وتُسمّى أيضًا المجموع البادئ أو المجموع التراكمي. المجموع الجاري لـ [3, 1, 4, 1, 5] هو [3, 4, 8, 9, 14].
ما هو التعقيد الزمني لحساب مجموع تراكمي؟
زمن O(n) باستخدام مجموع كلي واحد يُنقل من اليسار إلى اليمين، ومساحة إضافية O(1) بخلاف الإجابة. إعادة حساب كل بادئة من البداية تستغرق O(n²).
هل يمكنك حساب المجموع التراكمي في مكانه؟
نعم. انتقل من الفهرس 1 إلى النهاية وعيّن nums[i] += nums[i-1]. عندها تكون nums[i-1] قد أصبحت تحتوي على مجموع كل ما يسبقها، لذا ينتهي كل عنصر بوصفه المجموع التراكمي حتى موضعه. ستفقد القيم الأصلية.
كيف تساعد المجاميع التراكمية في الاستعلامات عن مجموع نطاق؟
مجموع الشريحة nums[l..r] هو prefix[r] - prefix[l-1]، أو prefix[r] عندما l = 0. في [3, 4, 8, 9, 14]، مجموع العناصر من الفهرس 2 إلى الفهرس 4 هو 14 - 4 = 10. يستغرق كل استعلام O(1) بعد مرور واحد يستغرق O(n).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def runningSum(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [3, 1, 4, 1, 5]
الإخراج المتوقع
[3, 4, 8, 9, 14]