Find Pivot Index
لديك مصفوفة من الأعداد الصحيحة nums. فهرس الارتكاز هو فهرس يتساوى عنده مجموع القيم الموجودة على يساره مع مجموع القيم الموجودة على يمينه. ولا تنتمي القيمة عند فهرس الارتكاز إلى أي من الجانبين، ويكون مجموع الجانب الذي لا يحتوي على قيم هو 0.
أعِد فهرس الارتكاز الأيسر، أو -1 إذا لم يكن أي فهرس فهرس ارتكاز.
الدالة
- numsinteger-array
- مصفوفة الأعداد الصحيحة المطلوب موازنتها
- تُرجعinteger
- مؤشر المحور الأيسر، أو -1 إن لم يوجد
القيود
1 ≤ nums.length ≤ 104-1000 ≤ nums[i] ≤ 1000
أمثلة
- المدخلات
- nums = [3, 1, 5, 2, 2]
- المخرجات
- 2
- الشرح
- عند الفهرس 2، يكون الطرف الأيسر 3 + 1 = 4 والطرف الأيمن 2 + 2 = 4. لا يتوازن الفهرس 0 والفهرس 1 (الطرف الأيسر 0 مقابل 10، والطرف الأيسر 3 مقابل 9)، لذا فإن 2 هو محور الارتكاز الأيسر.
- المدخلات
- nums = [1, 2, 3]
- المخرجات
- -1
- الشرح
- تعطي المرشحات الثلاثة 0 مقابل 5، و1 مقابل 3، و3 مقابل 0. لا يتوازن أيٌّ من الفهارس، لذا الإجابة هي
-1.
- المدخلات
- nums = [4, -4, 9]
- المخرجات
- 2
- الشرح
- عند الفهرس 2، يكون الجانب الأيسر 4 + (-4) = 0، والجانب الأيمن فارغ، لذا يكون مجموعه أيضًا 0. يمكن أن يكون الفهرس الأخير هو المحور.
+17 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك إيجاد المحور الأيسر مع قراءة كل قيمة مرة واحدة فقط، دون جمع القيم أولًا؟ وما تكلفة ذلك من حيث الذاكرة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
يتطلب فحص فهرس واحد مجموعين: القيم التي تسبقه والقيم التي تليه. وإعادة جمعها لكل فهرس تكرر معظم العمل. كيف يرتبط المجموعان للفهرس
iبالمجموعين للفهرسi+1؟إن التحرك خطوة واحدة إلى اليمين يضيف
nums[i]إلى المجموع الأيسر. وبمجرد معرفة مجموع المصفوفة بأكملها، يمكن استنتاج المجموع الأيمن من الأيسر: فهو المجموع الكلي ناقص المجموع الأيسر ناقصnums[i].اجمع عناصر المصفوفة كلها أولًا. ثم انتقل من اليسار إلى اليمين مع الاحتفاظ بمجموع جارٍ للعناصر الموجودة على اليسار. عند كل فهرس، قارن مجموع اليسار بالإجمالي مطروحًا منه مجموع اليسار والقيمة الحالية؛ أعد الفهرس عند أول تطابق، وبعد المقارنة فقط أضف القيمة الحالية إلى مجموع اليسار. إذا انتهت الحلقة، فأعد -1.
الحل
التحقق من فهرس واحد يتطلب حساب مجموعين، لكن إعادة حسابهما عند كل فهرس تجعل العمل يزداد مع مربع الطول. الحل هو التوقف عن إعادة الحساب: يزداد المجموع الأيسر بقيمة واحدة في كل خطوة، أما المجموع الأيمن فهو ما يتبقى من الإجمالي. تمريرة لحساب الإجمالي، ثم تمريرة ثانية مع مجموع أيسر متراكم، تحددان المحور الأيسر، مع الاحتفاظ بعددين في الذاكرة.
اجمع كلا الجانبين عند كل فهرس
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اتبع التعريف. لكل فهرس i، اجمع القيم التي تسبقه، واجمع القيم التي تليه، ثم قارن بين المجموعين. أول فهرس يتساوى عنده المجموعان هو الإجابة، لأنك تجرّب الفهارس من اليسار إلى اليمين.
الحافتان تتكفلان بأمرهما. عند الفهرس 0، تُنفَّذ الحلقة اليسرى صفر مرة، لذا يكون المجموع الأيسر 0؛ وعند الفهرس الأخير، تُنفَّذ الحلقة اليمنى صفر مرة. لهذا تُرجع [4, -4, 9] القيمة 2.
المشكلة هي التكلفة. عند كل فهرس، تُجمع القيم n-1 الأخرى، لذا يبلغ إجمالي العمل نحو n² عملية جمع. عند وجود 10,000 قيمة، يقترب العدد من 100 مليون عملية جمع، ومعظمها يعيد حساب مجاميع سبق أن حسبتها عند الفهرس السابق.
الخوارزمية
- كرّر الحلقة باستخدام
iعلى كل فهرس فيnums. - اجمع
nums[0]إلىnums[i-1]للحصول على المجموع الأيسر. - اجمع
nums[i+1]إلى القيمة الأخيرة للحصول على المجموع الأيمن. - إذا تساوى المجموعان، فأعد
i. - إذا لم يتطابق أي فهرس، فأعد -1.
def pivotIndex(nums):
n = len(nums)
for i in range(n):
left = 0
for j in range(i):
left += nums[j]
right = 0
for j in range(i + 1, n):
right += nums[j]
if left == right:
return i
return -1مصفوفة المجاميع التراكمية
الفكرة
تواصل طريقة القوة الغاشمة جمع قيم المقاطع في المصفوفة. تنجز مصفوفة المجاميع التراكمية هذا العمل مرة واحدة. لنعرّف prefix[k] بأنه مجموع أول k قيم، مع prefix[0] = 0. بالنسبة إلى [3, 1, 5, 2, 2]، تكون النتيجة [0, 3, 4, 9, 11, 13].
الآن، مجموع أي مقطع هو الفرق بين قيمتين. الجانب الأيسر من الفهرس i هو أول i قيم، لذا فهو prefix[i]. أما الجانب الأيمن فهو كل ما يأتي بعد nums[i]، أي prefix[n] - prefix[i+1]. عند الفهرس 2، يكون المجموع 4 على اليسار و13 - 9 = 4 على اليمين، وهذا يمثل نقطة ارتكاز.
يتطلب إنشاء المصفوفة مرورًا واحدًا، ويستغرق كل فحص وقتًا ثابتًا، لذا فإن البحث بأكمله يستغرق O(n). والتكلفة هي n+1 عددًا إضافيًا في الذاكرة.
الخوارزمية
- أنشئ
prefixبطولn+1معprefix[0] = 0. - املأه:
prefix[k+1] = prefix[k] + nums[k]. - لكل فهرس
i، اقرأ المجموع الأيسر على أنهprefix[i]والمجموع الأيمن على أنهprefix[n] - prefix[i+1]. - أعِد أول
iيتساوى عنده المجموعان، أو -1 بعد الحلقة.
def pivotIndex(nums):
n = len(nums)
# prefix[k] is the sum of the first k values.
prefix = [0] * (n + 1)
for k in range(n):
prefix[k + 1] = prefix[k] + nums[k]
for i in range(n):
left = prefix[i]
right = prefix[n] - prefix[i + 1]
if left == right:
return i
return -1المجموع الكلي والمجموع التراكمي من اليسار
الفكرة
انظر إلى إدخالات المجموع التراكمي التي يقرأها النهج السابق. عند الفهرس i يحتاج إلى prefix[i] وprefix[i+1] وprefix[n]. الأخير هو المجموع الكلي، وهو لا يتغير أبدًا، أما الاثنان الآخران فهما المجموع الجاري الذي ستحصل عليه إذا مررت على المصفوفة مرة واحدة. لذا يمكنك الاحتفاظ بالمجموع الكلي ومجموع جارٍ واحد للجهة اليسرى بدلًا من المصفوفة كاملة.
كل قيمة تقع على اليسار، أو عند المحور، أو على اليمين. لذا فإن مجموع الجهة اليمنى يساوي المجموع الكلي ناقص مجموع الجهة اليسرى ناقص nums[i]. بالنسبة إلى [3, 1, 5, 2, 2]، المجموع الكلي هو 13. عند الفهرس 0، مجموع الجهة اليسرى هو 0 ومجموع الجهة اليمنى هو 13 - 0 - 3 = 10. عند الفهرس 1، يكون المجموع 3 مقابل 9. وعند الفهرس 2، يكون 4 مقابل 13 - 4 - 5 = 4، لذا تُعيد 2.
الترتيب داخل الحلقة مهم. قارن أولًا، ثم أضف nums[i] إلى مجموع الجهة اليسرى، كي لا يتضمن هذا المجموع القيمة عند الفهرس الذي تختبره. الإرجاع عند أول تطابق يعطيك المحور الواقع في أقصى اليسار.
تقرأ المصفوفة مرتين، مرة لحساب المجموع الكلي ومرة لإجراء المسح، لذا فالزمن هو O(n). ولا تُخزَّن سوى قيمتين، لذا فالمساحة الإضافية هي O(1).
الخوارزمية
- اجمع كل قيمة في
total. - عيّن
leftإلى 0. - لكل فهرس
i، إذا كانleftيساويtotal - left - nums[i]، فأعِدi. - وإلا فأضف
nums[i]إلىleftوانتقل إلى الخطوة التالية. - إذا انتهت الحلقة، فأعِد -1.
def pivotIndex(nums):
total = sum(nums)
left = 0
for i, value in enumerate(nums):
# Everything that is not on the left and not nums[i] is on the right.
if left == total - left - value:
return i
left += value
return -1
أخطاء شائعة وحالات حدّية
تضع معظم الإجابات الخاطئة قيمة المحور نفسه في أحد الجانبين أو تتجاوز فهرسًا عند أحد الطرفين.
- إضافة
nums[i]إلى مجموع اليسار قبل المقارنة. عندئذٍ يتضمن الجانب الأيسر قيمة المحور، ولن تعثر[3, 1, 5, 2, 2]على الفهرس 2. - حساب الجانب الأيمن باستخدام
total - left. فهذا يحتسبnums[i]ضمن الجانب الأيمن؛ لذا اطرحها أيضًا. - تجاوز الفهرس 0 أو الفهرس الأخير. فكلاهما قد يكون المحور، لأن مجموع الجانب الفارغ يساوي 0. تُرجع
[1, -1, 1]القيمة 0، وتُرجع[4, -4, 9]القيمة 2. - إرجاع آخر تطابق بدلًا من الأول. في
[0, 0, 0]، يتوازن كل فهرس، والإجابة هي 0. - استخدام مؤشرين يتحركان نحو الداخل من الطرفين ويزيدان الجانب الأصغر. لا ينجح ذلك إلا عندما تكون كل القيم غير سالبة؛ أما هنا فتصل القيم إلى -1000، لذا قد يتقلص أحد الجانبين أثناء نموه.
- نسيان أن المصفوفات في Lua وR تبدأ من 1. أرجِع
i-1لتكون الإجابة فهرسًا يبدأ من 0.
أسئلة شائعة4
ما هو التعقيد الزمني لدالة Find Pivot Index؟
يعمل حل المجموع الكلي والمجموع التراكمي بزمن O(n): مرور واحد لجمع عناصر المصفوفة، ومرور واحد لفحصها. ويستخدم مساحة إضافية قدرها O(1). أما إعادة حساب كلا الجانبين عند كل فهرس فتستغرق زمنًا قدره O(n²).
لماذا يساوي المجموع الأيمن الإجمالي مطروحًا منه المجموع الأيسر وnums[i]؟
تقع كل قيمة في المصفوفة في موضع واحد بالضبط من ثلاثة مواضع: يسار i، أو عند i، أو يمين i. ومجموعها يساوي الإجمالي، لذا فإن مجموع الجزء الأيمن هو الإجمالي بعد طرح الجزأين الآخرين منه. وهذا يتيح لك التحقق من فهرس دون الحاجة إلى جمع قيم الجزء الأيمن مطلقًا.
هل يمكن حل مسألة إيجاد فهرس المحور باستخدام مؤشرين؟
ليس ذلك موثوقًا. يفترض المسح بمؤشرين، الذي يوسّع دائمًا الجانب الأصغر، أن إضافة قيمة تجعل الجانب أكبر، وهذا الافتراض لا يصح بمجرد أن تصبح القيم سالبة: فقد يتقلص الجانب أثناء توسيعه، وبالتالي قد يتجاوز المؤشر نقطة الارتكاز الحقيقية. لا تفترض طريقة المجموع التراكمي أي شيء عن الإشارات، وتتحقق من كل فهرس.
ما فهرس المحور لصفيف يحتوي على عنصر واحد؟
إنه 0. كلا جانبي العنصر الوحيد فارغان، ومجموع الجانب الفارغ يساوي 0، لذا فالجانبان متساويان. يُرجع حل المجموع التراكمي 0 عند أول مقارنة: قيمة اليسار هي 0، وكذلك المجموع مطروحًا منه 0 والقيمة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def pivotIndex(nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [3, 1, 5, 2, 2]
المتوقع
2