Check if an Array Is Sorted
لديك مصفوفة من الأعداد الصحيحة nums. أرجِع true إذا كانت مرتبة ترتيبًا غير تنازلي، أي إن كل عنصر أصغر من العنصر الذي يليه أو يساويه، وأرجِع false خلاف ذلك. لا بأس بتساوي العناصر المتجاورة: تُعد [2, 2, 3] مرتبة. المصفوفة التي تحتوي على عنصر واحد مرتبة.
الدالة
- numsinteger-array
- مصفوفة الأعداد الصحيحة المطلوب التحقق منها
- تُرجعboolean
- true عندما يكون كل عنصر أقل من العنصر الذي يليه أو مساويًا له، وfalse خلاف ذلك
القيود
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
أمثلة
- المدخلات
- nums = [1, 3, 3, 7]
- المخرجات
- true
- الشرح
- كل خطوة تصعد أو تبقى على المستوى نفسه: من 1 إلى 3، ومن 3 إلى 3، ومن 3 إلى 7. يُسمح بتكرار 3، لذا فالإجابة هي
true.
- المدخلات
- nums = [2, 5, 4, 9]
- المخرجات
- false
- الشرح
- الانتقال من 5 إلى 4 يكون نزولًا. تكفي خطوة واحدة كهذه لجعل المصفوفة غير مرتبة، رغم أن 9 في النهاية هي القيمة الأكبر، لذا فالإجابة هي
false.
سؤال إضافي
كيف يمكنك التحقق، في مرور واحد، مما إذا كان المصفوفة مرتبة تصاعديًا أو تنازليًا؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
إذا لم تكن المصفوفة مرتبة، فأين يمكنك ملاحظة ذلك فيها؟ هل تحتاج إلى مقارنة عناصر متباعدة؟
يكفي مقارنة كل عنصر بالعنصر الذي يليه مباشرةً. يُسمح بالعناصر المتجاورة المتساوية؛ وحدها الخطوة إلى الأسفل تخلّ بالترتيب.
كرّر على الأزواج المتجاورة وأعِد
falseعند أول زوج تكون فيه القيمة اليسرى أكبر من القيمة اليمنى. إذا لم يوجد مثل هذا الزوج، فأعِدtrue.
الحل
تكون المصفوفة مرتبة بالضبط عندما لا يكون أي عنصر أكبر من العنصر الذي يليه مباشرةً. لا تحتاج أبدًا إلى مقارنة عناصر متباعدة: إذا كان كل زوج متجاور مرتبًا، فالمصفوفة بأكملها مرتبة. وهذا يحوّل التحقق إلى مرور واحد على n-1 زوجًا، ويمكن إيقافه عند أول تراجع.
رتّب نسخة وقارِن
الفكرة
المصفوفة المرتبة هي مصفوفة لن يتغير ترتيبها عند فرزها. لذا أنشئ نسخة من nums، ثم افرز النسخة وتحقق مما إذا كانت تطابق المصفوفة الأصلية موضعًا بموضع. إذا تطابقت جميع المواضع، فهذا يعني أن nums كانت مرتبة بالفعل.
بالنسبة إلى [2, 5, 4, 9]، تكون النسخة المرتبة [2, 4, 5, 9]. يحتوي الموضع 1 على 5 في المصفوفة الأصلية وعلى 4 في النسخة، لذا تكون الإجابة false. أما بالنسبة إلى [1, 3, 3, 7]، فالنسخة مطابقة للمصفوفة الأصلية، وتكون الإجابة true.
هذا صحيح، لكنه يفعل أكثر مما يتطلبه السؤال. يستغرق الفرز O(n log n)، أي نحو 6 × 10^4 مقارنةً لـ 5000 عدد، كما تستهلك النسخة ذاكرةً مقدارها O(n). ويقرأ أيضًا المصفوفة بأكملها دائمًا، حتى لو كان الزوج الأول غير مرتب.
الخوارزمية
- انسخ
numsحتى تبقى النسخة الأصلية دون تغيير. - رتّب النسخة تصاعديًا حسب القيمة العددية.
- قارن النسخة مع
numsموضعًا بموضع. - أعِد
trueإذا تطابق كل موضع، وإلا فأعِدfalse.
def isSorted(nums):
# sorted returns a new list, so nums itself is left as it was.
return sorted(nums) == numsقارن كل زوج من العناصر المتجاورة
الفكرة
لا تحتاج إلى النسخة المرتبة لمعرفة ما إذا كانت المصفوفة مرتبة. تكون المصفوفة مرتبة ترتيبًا غير تنازلي بالضبط عندما يكون كل عنصر أقل من أو يساوي العنصر الذي يليه مباشرةً. وبما أن علاقات ≤ متعدية (a ≤ b وb ≤ c تعنيان a ≤ c)، فإن التحقق من أزواج العناصر المتجاورة وعددها n-1 يغطي كل زوج من المواضع.
مرّر i من 1 إلى n-1 وقارن nums[i-1] مع nums[i]. في المصفوفة [2, 5, 4, 9]، الزوج (2, 5) سليم، لكن الزوج (5, 4) يتناقص، لذا تُعيد false عندها مباشرةً من دون النظر إلى 9. الأزواج المتجاورة المتساوية تجتاز الاختبار، لأن الشرط الوحيد الذي يفشل هو >.
تُقارَن كل العناصر في الأزواج مرة واحدة، لذا يكون الزمن O(n)، ويكون متغير الحلقة هو الذاكرة الإضافية الوحيدة، O(1). قارن القيمتين مباشرةً بدلًا من طرح إحداهما من الأخرى: فمع قيم تصل إلى 10^9، قد يتجاوز الفرق نطاق عدد صحيح من نوع int ذي 32 بت.
الخوارزمية
- كرّر
iمن 1 إلىn-1. - إذا كان
nums[i-1] > nums[i]، فأرجِعfalse. - إذا انتهت الحلقة، فأرجِع
true. يتجاوز العنصر الواحد الحلقة ويكون مرتبًا.
def isSorted(nums):
for i in range(1, len(nums)):
# One step down anywhere breaks the order.
if nums[i - 1] > nums[i]:
return False
return True
أخطاء شائعة وحالات حدّية
الحلقة قصيرة، لذا تكمن الأخطاء عند أطرافها وفي المقارنة.
- اعتبار العناصر المتجاورة المتساوية حالة فشل. اختبار
nums[i-1] >= nums[i]يرفض[1, 3, 3, 7]. لا يكسر الترتيب إلا الانخفاض الصارم (>). - القراءة بعد نهاية المصفوفة. يجب أن تتوقف الحلقة التي تمتد من
0إلىn-1وتقارنnums[i]بـnums[i+1]قبل النهاية بعنصر واحد، وإلا فستقرأ خارج المصفوفة. البدء منi = 1والمقارنة معi-1يتجنب هذه المشكلة. - الطرح بدلًا من المقارنة. يبدو
nums[i] - nums[i-1] >= 0مماثلًا، لكن10^9 - (-10^9) = 2 × 10^9لا يتسع في عدد صحيح من 32 بت، ويلتف ليصبح عددًا سالبًا، لذا يُبلّغ خطأً عن أن[-1000000000, 1000000000]غير مرتبة. كما أن التجاوز نفسه يكسر دالة مقارنة qsort المكتوبة بصيغةx - y. - ترتيب الأعداد كما لو كانت نصوصًا. في JavaScript، يؤدي استدعاء
sort()من دون دالة مقارنة إلى وضع10قبل9، لذا تعطي عملية الترتيب ثم المقارنة إجابات خاطئة.
أسئلة شائعة3
كيف تتحقق مما إذا كانت المصفوفة مرتبة؟
قارن كل عنصر بالعنصر الذي يليه. إذا كان أي عنصر أكبر من جاره على اليمين، فالمصفوفة غير مرتبة ويمكنك التوقف؛ وإذا وصلت إلى النهاية دون العثور على عنصر كهذا، فهي مرتبة. يستغرق ذلك وقتًا قدره O(n) ومساحة إضافية قدرها O(1).
لماذا يكفي التحقق من الخلايا المجاورة؟
علاقة الترتيب متعدية: إذا كان a ≤ b وb ≤ c، فإن a ≤ c. لذا، عندما يكون كل زوج متجاور مرتبًا، يكون كل زوج من المواضع مرتبًا أيضًا. وعلى العكس، يحتوي أي مصفوفة غير مرتبة على الأقل على زوج متجاور واحد تنخفض فيه القيمة.
هل تكون المصفوفة التي تحتوي على عناصر متساوية مرتبة؟
بترتيب غير تنازلي، نعم: [4, 4, 4] مرتبة لأنه لا يوجد عنصر أكبر من العنصر الذي يليه. إذا طلبت المسألة ترتيبًا تصاعديًا صارمًا بدلًا من ذلك، فغيّر الاختبار ليرفض العناصر المتجاورة المتساوية أيضًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def isSorted(nums):
# اكتب الكود هنااختبار #1
اختبار #2
وسيط
nums = [1, 3, 3, 7]
الإخراج المتوقع
true