Product of Array Except Self
لديك مصفوفة من الأعداد الصحيحة nums. أعد مصفوفة answer بالطول نفسه، بحيث تكون answer[i] حاصل ضرب كل عنصر في nums باستثناء العنصر الموجود عند الفهرس i. نفّذ ذلك في زمن O(n) ومن دون استخدام القسمة.
الدالة
- numsinteger-array
- مصفوفة الأعداد الصحيحة، التي تحتوي على عنصرين على الأقل
- تُرجعinteger-array
- مصفوفة تكون قيمتها عند الفهرس i حاصل ضرب جميع العناصر باستثناء nums[i]
القيود
2 ≤ nums.length ≤ 104-30 ≤ nums[i] ≤ 30- حاصل ضرب جميع القيم غير الصفرية في
numsيقع ضمن نطاق عدد صحيح موقّع من 32 بت، لذا فإن كل حاصل ضرب تحسبه في أثناء ذلك يقع ضمن هذا النطاق أيضًا.
أمثلة
- المدخلات
- nums = [2, 3, 4, 5]
- المخرجات
- [60, 40, 30, 24]
- الشرح
- عند استبعاد العدد 2، يتبقى 3 × 4 × 5 = 60، وعند استبعاد العدد 5، يتبقى 2 × 3 × 4 = 24. وينطبق الأمر نفسه على العددين الأوسطين: 2 × 4 × 5 = 40 و2 × 3 × 5 = 30.
- المدخلات
- nums = [-2, 5, 0, 3]
- المخرجات
- [0, 0, -30, 0]
- الشرح
- كل حاصل ضرب يتضمن 0 يساوي 0. حاصل الضرب الوحيد الذي يستثني 0 هو الخاص بالفهرس 2، ويساوي -2 × 5 × 3 = -30.
- المدخلات
- nums = [0, 4, 0, -1]
- المخرجات
- [0, 0, 0, 0]
- الشرح
- مع وجود صفرين، يظل كل حاصل ضرب يتضمن صفرًا واحدًا منهما على الأقل، لذا تكون كل قيمة في الإجابة 0.
+14 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك استخدام مساحة إضافية O(1) فقط، دون احتساب المصفوفة التي تُعيدها؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
يعمل ضرب جميع القيم الأخرى لكل فهرس، لكن مع 10,000 قيمة فهذا يعني نحو 100 مليون عملية ضرب، ومعظمها يتكرر. ما القاسم المشترك بين حاصل الضرب للفهرس
iوحاصل الضرب للفهرسi + 1؟كل شيء باستثناء
nums[i]ينقسم إلى القيم التي على يساره والقيم التي على يمينه. إذا كنت تعرف حاصل ضرب كل بادئة وكل لاحقة، فستحتاج إلى عملية ضرب واحدة لكل إجابة.املأ مصفوفة الإجابة من اليسار بحاصل ضرب القيم التي تسبق كل فهرس، بدءًا من 1. ثم مرّ عليها من اليمين مع حاصل ضرب تراكمي واحد للقيم التي تلي الفهرس: اضربه في الإجابة أولًا، ثم اضرب فيه
nums[i].
الحل
حاصل ضرب كل شيء باستثناء nums[i] هو حاصل ضرب القيم على يساره مضروبًا في حاصل ضرب القيم على يمينه. تبدو قسمة حاصل الضرب الكلي على nums[i] أقصر، لكنها غير مسموح بها هنا، كما أنها لا تعمل عند وجود أصفار، إذ يكون حاصل الضرب الكلي عندها 0. تتيح جداءات البادئات واللواحق حساب جميع جداءات القيم على اليسار واليمين في مرورين، لذا يستغرق الحل O(n) من الوقت. يمكن أن تحتوي مصفوفة الناتج على جداءات القيم على اليسار، ويحمل متغير واحد حاصل ضرب القيم على اليمين، لذلك لا حاجة إلى أي مصفوفة أخرى.
اضرب القيم الأخرى لكل فهرس
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اتبع التعريف. لكل فهرس i، ابدأ حاصل الضرب من 1 واضرب فيه كل nums[j] الذي لا يكون فهرسه j مساويًا لـ i. إن تخطي ذلك الفهرس، بدلًا من القسمة عليه لاحقًا، يجعل الأصفار غير مؤذية: في [-2, 5, 0, 3]، لا يرى حاصل الضرب عند الفهرس 2 القيمة 0 أبدًا، وتكون نتيجته -30.
هذا صحيح، لكنه يكرر العمل. حاصلَا الضرب عند الفهرسين 0 و1 يشتركان في كل القيم باستثناء اثنتين، ومع ذلك تعيد ضربها كلها. يتطلب كل موضع من المواضع n عدد n-1 من عمليات الضرب، أي نحو 10^8 عملية إجمالًا عندما تكون n = 10^4. تنجز C ذلك في جزء من الثانية، لكن Python وRuby وR تستغرق وقتًا طويلًا جدًا.
الخوارزمية
- أنشئ مصفوفة إجابة طولها n.
- لكل فهرس
i، عيّن قيمةproductإلى 1. - اضرب
productفي كلnums[j]يكون فهرسهjمختلفًا عنi. - خزّن
productعند الفهرسiفي مصفوفة الإجابة. - أعِد مصفوفة الإجابة.
def productExceptSelf(nums):
n = len(nums)
answer = []
for i in range(n):
product = 1
for j in range(n):
if j != i:
product *= nums[j]
answer.append(product)
return answerمصفوفات حاصل ضرب البادئات واللواحق
الفكرة
قسّم حاصل الضرب عند الفهرس i إلى جزأين: القيم التي تسبق i والقيم التي تليه. سمِّ حاصلي الضرب هذين before[i] وafter[i]. عندها answer[i] = before[i] × after[i]، ويُستثنى nums[i] من دون إجراء أي قسمة.
تنمو كل مصفوفة انطلاقًا من العنصر المجاور لها باستخدام عملية ضرب واحدة. before[0] تساوي 1، وهو حاصل ضرب لا شيء من القيم، وbefore[i] = before[i-1] × nums[i-1]. ومن الطرف الآخر، after[n-1] تساوي 1 وafter[i] = after[i+1] × nums[i+1]. بالنسبة إلى [2, 3, 4, 5]، تحصل على before = [1, 2, 6, 24] وafter = [60, 20, 5, 1]، ويعطي ضربهما عنصرًا بعنصر [60, 40, 30, 24].
تتطلب ثلاث تمريرات، كل منها من n خطوة، زمنًا قدره O(n). وتستهلك مصفوفتا المساعدة O(n) من الذاكرة الإضافية، وهو ما تلغيه الطريقة التالية.
الخوارزمية
- املأ
beforeمن اليسار:before[0] = 1، ثم تكون كل خانة حاصل ضرب الخانة السابقة في القيمة السابقة. - املأ
afterمن اليمين:after[n-1] = 1، ثم تكون كل خانة حاصل ضرب الخانة التالية في القيمة التالية. - عيّن
answer[i]إلىbefore[i] × after[i]لكل فهرس. - أعِد
answer.
def productExceptSelf(nums):
n = len(nums)
# before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
before = [1] * n
after = [1] * n
for i in range(1, n):
before[i] = before[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
after[i] = after[i + 1] * nums[i + 1]
return [before[i] * after[i] for i in range(n)]المنتج الأيسر في الإجابة، ومنتج أيمن واحد جارٍ
الفكرة
لست بحاجة أبدًا إلى مصفوفة after كاملة دفعةً واحدة. عند المرور بدءًا من الطرف الأيمن، يكون حاصل ضرب القيم الواقعة إلى يمين i عددًا واحدًا. احتفظ به في متغير right وحدّثه بضربة ضرب واحدة في كل خطوة.
لذا اكتب حواصل الضرب اليسرى مباشرةً في مصفوفة الإجابة في المرور الأول. في المرور الثاني من اليمين، اضرب answer[i] في right، ثم اضرب right في nums[i]. الترتيب مهم: عند استخدام right عند الفهرس i، يجب ألا يتضمن nums[i] بعد.
بالنسبة إلى [2, 3, 4, 5]، يترك المرور الأول المصفوفة [1, 2, 6, 24]. يستخدم المرور الثاني القيم right = 1، 5، 20، 60 عند الفهارس 3، 2، 1، 0، ويحوّل المصفوفة إلى [60, 40, 30, 24]. يظل الزمن O(n)، وبالإضافة إلى المصفوفة التي تُعيدها، لا تحتاج الذاكرة الإضافية إلا إلى متغير واحد: O(1).
الخوارزمية
- عيّن
answer[0] = 1، ثم من اليسار إلى اليمين عيّنanswer[i] = answer[i-1] × nums[i-1]. - عيّن
rightإلى 1. - من الفهرس الأخير نزولًا إلى 0، اضرب
answer[i]فيright. - ثم اضرب
rightفيnums[i]. - أعِد
answer.
def productExceptSelf(nums):
n = len(nums)
# Pass 1: answer[i] = product of everything left of i
answer = [1] * n
for i in range(1, n):
answer[i] = answer[i - 1] * nums[i - 1]
# Pass 2: multiply in the product of everything right of i
right = 1
for i in range(n - 1, -1, -1):
answer[i] *= right
right *= nums[i]
return answer
أخطاء شائعة وحالات حدّية
تنتج الأخطاء هنا عن الأصفار، وترتيب عمليتي التحديث في المرور الثاني، وحدود المصفوفة.
- يفشل قسمة حاصل الضرب الكلي على
nums[i]بمجرد ظهور 0. في[-2, 5, 0, 3]يكون الحاصل الكلي 0، وعند الفهرس 2 ستحتاج إلى قسمة 0 على 0. يمكن معالجة ذلك بعدّ الأصفار، لكن المسألة تمنع القسمة على أي حال. - ضرب
rightفيnums[i]قبل استخدامه يُدخلnums[i]في حاصل ضربه هو نفسه. في[2, 3, 4, 5]تصبح القيمة الأخيرة 120 بدلًا من 24. - بدء حواصل الضرب اليسرى من
nums[0]بدلًا من 1. لا يوجد شيء إلى يسار الفهرس 0، لذا فإن حاصل الضرب إلى يساره هو حاصل الضرب الفارغ، أي 1، وينتهي الأمر بأن تكونanswer[0]حاصل ضرب القيم التي إلى يمينه فقط. - حدود الحلقات: يقرأ المرور من اليسار
nums[i-1]، لذا يبدأ عند الفهرس 1. وتقرأ مصفوفة اللواحقnums[i+1]، لذا تبدأ عند الفهرس n-2. - يجعل وجود صفرين كل إجابة تساوي 0. أما وجود صفر واحد فيجعل كل الإجابات 0، باستثناء الإجابة عند فهرس الصفر نفسه. اختبر الحالتين قبل أن تثق بشيفرتك.
أسئلة شائعة4
ما التعقيد الزمني لمسألة حاصل ضرب المصفوفة باستثناء العنصر الحالي؟
يعمل حل البادئات واللواحق بزمن O(n): مرور واحد من اليسار ومرور واحد من اليمين. ومع تخزين جداءات اليسار في مصفوفة الإخراج وجدء يمين جارٍ واحد، يحتاج إلى مساحة إضافية O(1) عدا مصفوفة الإخراج. يستغرق ضرب جميع القيم الأخرى لكل فهرس زمنًا قدره O(n²).
لماذا لا يُسمح بالقسمة في حاصل ضرب عناصر المصفوفة باستثناء العنصر نفسه؟
تؤدي قسمة حاصل ضرب جميع العناصر على nums[i] إلى حدوث مشكلة عندما تحتوي المصفوفة على صفر، لأن حاصل الضرب الكلي يساوي 0، كما أن الفهرس الخاص بالصفر نفسه يتطلب القسمة على 0. ويتطلب جعلها تعمل حساب عدد الأصفار والتعامل مع حالات خاصة. وتوجّهك هذه القاعدة نحو حاصلَي الضرب البادئي واللاحقي، اللذين يتعاملان مع الأصفار دون أي حالات خاصة على الإطلاق.
هل تُحتسب مصفوفة الإخراج مساحةً إضافية؟
لا. عليك إرجاع الإجابة على أي حال، لذا لا يحتسبها العرف المعتاد ضمن المساحة. لذلك، فإن تخزين النواتج اليسرى فيها والاحتفاظ بالناتج الأيمن في متغير واحد يُعدّ استخدامًا لمساحة إضافية مقدارها O(1).
كيف تتعامل دالة حاصل ضرب عناصر المصفوفة باستثناء العنصر نفسه مع الأصفار؟
مع حاصل ضرب البادئات واللواحق، لا حاجة إلى معالجة خاصة للأصفار. أي حاصل ضرب من اليسار أو اليمين يتجاوز صفرًا تكون قيمته 0، بينما يتخطى حاصل الضرب عند فهرس الصفر نفسه ذلك الصفر. عند وجود صفرين أو أكثر، يحتوي كل حاصل ضرب على صفر، لذا تكون كل الإجابات 0.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def productExceptSelf(nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [2, 3, 4, 5]
المتوقع
[60, 40, 30, 24]