Squares of a Sorted Array
لديك مصفوفة من الأعداد الصحيحة nums مرتبة ترتيبًا غير تنازلي. قد تحتوي على قيم سالبة. ربّع كل قيمة وأعِد المربعات في مصفوفة جديدة، مرتبة أيضًا ترتيبًا غير تنازلي.
الدالة
- numsinteger-array
- المصفوفة المرتبة من الأعداد الصحيحة، بما في ذلك الأعداد السالبة
- تُرجعinteger-array
- مربع كل قيمة، مرتبة ترتيبًا غير تنازلي
القيود
1 ≤ nums.length ≤ 4000-104 ≤ nums[i] ≤ 104numsمرتبة ترتيبًا غير تنازلي.
أمثلة
- المدخلات
- nums = [-6, -2, 1, 3, 7]
- المخرجات
- [1, 4, 9, 36, 49]
- الشرح
- مربعات القيم بالترتيب الأصلي هي 36 و4 و1 و9 و49. تعطي القيم السالبة -6 و-2 مربعات كبيرة، لذا ينقل الفرز 36 إلى قرب النهاية:
[1, 4, 9, 36, 49].
- المدخلات
- nums = [-9, -4, -1]
- المخرجات
- [1, 16, 81]
- الشرح
- كل قيمة سالبة، لذا تظهر المربعات بترتيب عكسي: 81، 16، 1 تصبح
[1, 16, 81].
+14 اختبارات مخفية عند الإرسال
سؤال إضافي
يستغرق التربيع والترتيب O(n log n). هل يمكنك فعل ذلك في O(n)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ارفع عناصر
[-6, -2, 1, 3, 7]إلى المربع يدويًا. أي جزء من المصفوفة يفقد ترتيبه، ولماذا؟يأتي المربع الأكبر دائمًا من القيمة الأولى أو القيمة الأخيرة في
nums، لأن هاتين القيمتين هما الأبعد عن 0.ضع مؤشرًا عند كل طرف. قارن بين المربعين، واكتب المربع الأكبر في نهاية النتيجة، ثم حرّك ذلك المؤشر إلى الداخل. كرّر ذلك حتى تمتلئ جميع المواضع.
الحل
التربيع يحافظ على ترتيب القيم غير السالبة، لكنه يعكس ترتيب القيم السالبة، لذا لا تكون المربعات مرتبة. إعادة ترتيبها تصاعديًا تنجح، لكنها تتجاهل الترتيب الذي أُعطيت به. الحقيقة الأساسية: أكبر مربع يأتي دائمًا من أحد طرفي nums. قارن بين الطرفين، وضع المربع الأكبر في نهاية النتيجة، ثم تحرّك نحو الداخل.
ربّع، ثم رتّب
الفكرة
أنشئ مصفوفة جديدة تحتوي على مربع كل قيمة، ثم رتّبها. المربعات ليست سالبة أبدًا، والترتيب يضعها في تسلسل بصرف النظر عن مصدرها.
بالنسبة إلى [-6, -2, 1, 3, 7]، تكون المربعات [36, 4, 1, 9, 49]، ويعطي الترتيب [1, 4, 9, 36, 49].
تبلغ كلفة الترتيب O(n log n). وهذا سريع بما يكفي هنا، لكنه يتعامل مع المدخلات كما لو لم يكن لها أي ترتيب. تستخدم الطريقة التالية الترتيب وتحتاج إلى مرور واحد.
الخوارزمية
- أنشئ مصفوفة تحتوي على
x * xلكلxفيnums. - رتّبها ترتيبًا رقميًا تصاعديًا.
- أعِدها.
def sortedSquares(nums):
return sorted(x * x for x in nums)مؤشران من كلا الطرفين
الفكرة
اعتبر المربعات مسافة كل قيمة عن 0 بعد تربيعها. في المصفوفة المرتبة، تقع القيم الأبعد عن 0 عند الطرفين: القيمة الأكثر سلبية على اليسار، والقيمة الأكثر إيجابية على اليمين. لذا فإن أكبر مربع هو nums[left]² أو nums[right]²، وليس أي قيمة بينهما.
أبقِ left عند 0 وright عند n-1، واملأ النتيجة بدءًا من موضعها الأخير إلى الخلف. في كل خطوة، قارن مربعي الطرفين، واكتب الأكبر في الموضع الحالي، ثم حرّك ذلك المؤشر نحو الداخل. ما يتبقى بين المؤشرين هو مصفوفة مرتبة أيضًا، لذا تنطبق الحقيقة نفسها في كل خطوة.
في [-6, -2, 1, 3, 7]: تتفوق 49 على 36 وتذهب إلى الموضع الأخير. ثم تتفوق 36 على 9، و9 على 4، و4 على 1، ويملأ العدد 1 الموضع 0. النتيجة هي [1, 4, 9, 36, 49]. يوضع كل عنصر مرة واحدة: الزمن O(n)، والنتيجة هي المصفوفة الإضافية الوحيدة.
الخوارزمية
- أنشئ مصفوفة نتائج طولها
n. عيّنleftإلى 0 وrightإلىn-1. - تحرّك عبر المواضع من
n-1نزولًا إلى 0 باستخدامpos. - قارن
nums[left]²معnums[right]². - اكتب المربع الأكبر عند
posوحرّك المؤشر المقابل خطوةً نحو الداخل. - أعِد النتيجة.
def sortedSquares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
# the largest square left is always at one of the two ends
for pos in range(n - 1, -1, -1):
left_sq = nums[left] * nums[left]
right_sq = nums[right] * nums[right]
if left_sq > right_sq:
result[pos] = left_sq
left += 1
else:
result[pos] = right_sq
right -= 1
return result
أخطاء شائعة وحالات حدّية
نسخة المؤشرين قصيرة، لكن بعض التفاصيل تُفسدها.
- ملء النتيجة من الأمام. يقع أصغر مربع عند النقطة التي تعبر فيها القيم الصفر، وقد تكون هذه النقطة في أي موضع في المنتصف. لا يخبرك الطرفان إلا بأكبر مربع. املأ النتيجة من الخلف.
- مقارنة
nums[left]بـnums[right]بدلًا من مقارنة مربعيهما أو قيمتيهما المطلقَتين. العدد -6 أصغر من 3، لكن مربعه أكبر. - التوقف عندما يلتقي
leftبـright. عند تساويهما، تظل هناك قيمة واحدة لم توضع بعد؛ كرر المرور على كل موضع في النتيجة، أو استخدمleft <= right. - إدخال تكون قيمه كلها سالبة أو كلها موجبة. مع
[-9, -4, -1]يتولى المؤشر الأيسر كل العمل، ومع[2, 5, 8]يتولاه المؤشر الأيمن. ومع ذلك، يجب أن ينتج كلاهما مخرجات مرتبة. - في JavaScript وTypeScript، ترتب
sort()الأعداد كنصوص إذا لم تُمرر إليها دالة مقارنة، لذا تصبح[1, 4, 36, 9][1, 36, 4, 9]. مرر(a, b) => a - b.
أسئلة شائعة4
ما التعقيد الزمني لمربعات مصفوفة مرتبة؟
يعمل حل المؤشرين في زمن O(n): تُربَّع كل قيمة وتوضع مرة واحدة. أما التربيع ثم الفرز فيستغرق O(n log n). ويستخدم كلاهما ذاكرة O(n) للنتيجة.
لماذا يأتي المربع الأكبر من إحدى النهايتين؟
يزداد مربع العدد كلما زادت المسافة عن 0. في مصفوفة مرتبة، تكون القيمة الأبعد عن 0 من جهة الأعداد السالبة هي الأولى، والقيمة الأبعد عن 0 من جهة الأعداد الموجبة هي الأخيرة. وكل قيمة بينهما أقرب إلى 0 من إحدى هاتين القيمتين، لذا لا يمكن أن يكون مربعها هو الأكبر.
هل يمكنك ملء النتيجة بدءًا من الأمام بدلًا من ذلك؟
نعم، لكن عليك أولًا العثور على الموضع الذي تعبر فيه القيم الصفر، مثلًا باستخدام البحث الثنائي. بعد ذلك، يتحرك مؤشّران إلى الخارج انطلاقًا من تلك النقطة، كما عند دمج قائمتين مرتبتين: تُقرأ القيم السالبة من اليمين إلى اليسار، والقيم غير السالبة من اليسار إلى اليمين. يجنّبك ملء المصفوفة من الخلف عملية البحث، لأن مواضع النهايتين معروفة منذ البداية.
هل تُعَدّ مسألة مربعات مصفوفة مرتبة مسألة دمج؟
نعم، ولكن بشكل غير مباشر. تُشكّل مربعات القيم السالبة قائمة مرتبة واحدة (تُقرأ من اليمين إلى اليسار)، وتُشكّل مربعات القيم غير السالبة قائمة أخرى. ودمجهما هو خطوة الدمج في خوارزمية الفرز بالدمج، ولهذا يمكن إنجاز ذلك في مرور خطي واحد.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def sortedSquares(nums):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
nums = [-6, -2, 1, 3, 7]
المتوقع
[1, 4, 9, 36, 49]