Find the Largest Number
لديك قائمة غير فارغة من الأعداد الصحيحة nums. أعد أكبر قيمة فيها. يمكن أن تكون القيم سالبة، لذا قد تكون الإجابة سالبة أيضًا. اعثر عليها باستخدام المقارنات بنفسك، من دون دالة مدمجة لإيجاد القيمة العظمى مثل max.
الدالة
- numsinteger-array
- قائمة الأعداد الصحيحة التي سيتم البحث فيها
- تُرجعinteger
- أكبر قيمة في nums
القيود
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
أمثلة
- المدخلات
- nums = [3, 17, 4, 12, 9]
- المخرجات
- 17
- الشرح
- عند القراءة من اليسار، تكون أكبر قيمة حتى الآن هي
3، ثم17. لا تتجاوز أي من4أو12أو9القيمة17، لذا فالإجابة هي17.
- المدخلات
- nums = [-8, -3, -11, -3]
- المخرجات
- -3
- الشرح
- كل القيم سالبة، و
-3هو الأقرب إلى الصفر، لذا فهو الأكبر. يظهر مرتين، لكنك تُرجع القيمة، لا موضعها.
- المدخلات
- nums = [42]
- المخرجات
- 42
- الشرح
- القائمة التي تحتوي على قيمة واحدة، تكون تلك القيمة هي الأكبر فيها.
سؤال إضافي
هل يمكنك إرجاع أكبر قيمة وأصغر قيمة مع نحو 3n/2 مقارنةً بدلًا من 2n، وذلك بمقارنة القيم في أزواج أولًا؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اقرأ القيم واحدة تلو الأخرى. ما الشيء الوحيد الذي عليك تذكّره بشأن القيم التي رأيتها بالفعل؟
تذكّر أكبر قيمة حتى الآن فقط. كل قيمة جديدة إما أن تتجاوزها أو لا.
ابدأ الحد الأقصى الجاري عند
nums[0]، وليس عند0، لأن كل القيم قد تكون سالبة. قارنه بكل قيمة واحتفظ بالأكبر.
الحل
قد تكون أي قيمة تتجاوزها هي الأكبر، لذا يقرأ كل حل كل عنصر مرة واحدة على الأقل. القرار الفعلي الوحيد هو من أين تبدأ القيمة العظمى الحالية. ابدأها بالعنصر الأول، وليس أبدًا عند 0، لأن كل قيمة في القائمة قد تكون سالبة.
رتّب نسخةً وخذ القيمة الأخيرة
الفكرة
في قائمة مرتبة من الأصغر إلى الأكبر، تكون أكبر قيمة في النهاية. انسخ nums حتى تبقى قائمة المستدعِي كما هي، ثم رتّب النسخة وأعِد عنصرها الأخير. بالنسبة إلى [3, 17, 4, 12, 9] تكون النسخة المرتبة [3, 4, 9, 12, 17]، وعنصرها الأخير هو 17.
الإجابة صحيحة، لكن الترتيب ينفّذ أكثر بكثير مما تحتاج إليه. فهو يرتّب كل قيمة، وهذا يستغرق نحو n log n مقارنة، أي ما يقارب 60,000 مقارنة عندما تكون n = 5000، بينما لا تريد سوى أكبر قيمة. كما أن النسخ يستهلك ذاكرة مقدارها O(n).
في JavaScript وTypeScript، مرّر دالة مقارنة إلى sort. من دونها، تُقارَن الأعداد كنصوص، ما يجعل 12 و17 يسبقان 3.
الخوارزمية
- انسخ
nums. - رتّب النسخة تصاعديًا، مع مقارنة الأعداد بوصفها أعدادًا.
- أعِد العنصر الأخير من النسخة المرتّبة.
def findMax(nums):
ordered = sorted(nums) # a sorted copy, smallest first
return ordered[-1]تمريرة واحدة مع حدّ أقصى جارٍ
الفكرة
احتفِظ بمتغير واحد، largest، لأكبر قيمة ظهرت حتى الآن. ابدأه بالقيمة nums[0]، وقارنه بكل قيمة، واستبدله كلما كانت قيمة ما أكبر. عند انتهاء الحلقة، يكون largest قد قورن بكل عنصر، لذا لا توجد قيمة في القائمة أكبر منه.
بالنسبة إلى [3, 17, 4, 12, 9]، يبدأ largest بالقيمة 3، ويصبح 17، ويظل 17 عند المرور على 4 و12 و9. وهذا يعني إجراء n-1 مقارنة مفيدة واستخدام متغير إضافي واحد.
البدء بالقيمة nums[0] هو ما يجعل القوائم ذات الأعداد السالبة تعمل. إذا بدأت بالقيمة 0 بدلًا من ذلك، فلن تتجاوزها أبدًا القيم في [-8, -3, -11, -3]، لذا ستُرجع 0، وهي قيمة ليست موجودة أصلًا في القائمة.
الخوارزمية
- عيّن
largestإلىnums[0]. - كرّر على كل قيمة
xفيnums. - إذا كان
x > largest، فعيّنlargestإلىx. - بعد الحلقة، أعد
largest.
def findMax(nums):
largest = nums[0] # never 0: every value may be negative
for x in nums:
if x > largest:
largest = x
return largest
أخطاء شائعة وحالات حدّية
الحلقة قصيرة، لذا تكمن الأخطاء في موضع بدايتها وما تقرؤه.
- بدء
largestعند0أو-1. أي قائمة تكون جميع قيمها أقل من قيمة البداية هذه ستُرجع عددًا غير موجود في القائمة. - البدء بعدد صغير اعتباطي مثل
-1000000. تنخفض القيم هنا إلى-10^9، لذا تظل قيمة البداية هي الأكبر. لا حاجة إلى التخمين؛ استخدمnums[0]. - قراءة
nums[0]في Lua أو R، حيث يكون العنصر الأول هوnums[1]. تُرجع Lua القيمةnil، بينما تُرجع R متجهًا فارغًا. - التكرار باستخدام
i ≤ nفي لغة تستخدم فهارس تبدأ من 0، ما يؤدي إلى قراءة عنصر واحد بعد نهاية القائمة. - الفرز دون مُقارِن رقمي في JavaScript أو TypeScript. ينتهي الترتيب النصي للقائمة
[3, 17, 4, 12, 9]بالقيمة9، لذا ستُرجع9بدلًا من17.
أسئلة شائعة3
ما هو التعقيد الزمني لإيجاد القيمة العظمى في مصفوفة؟
تستغرق عملية المرور الواحدة زمنًا قدره O(n) ومساحة إضافية قدرها O(1). لا يمكن لأي طريقة على مصفوفة غير مرتبة أن تحقق أداءً أفضل، لأن أي عنصر لا تقرأه قد يكون الأكبر. يتطلب الفرز أولًا زمنًا قدره O(n log n)، وهو أبطأ من دون أي فائدة.
كيف تجد أكبر رقم في مصفوفة دون استخدام max؟
خزّن العنصر الأول في متغير. مرّ على بقية العناصر، وكلما كان أحد العناصر أكبر من قيمة المتغير، خزّن ذلك العنصر بدلًا منها. عند انتهاء الحلقة، سيحتوي المتغير على أكبر قيمة.
لماذا يجب أن تبدأ القيمة القصوى الجارية عند العنصر الأول، لا عند 0؟
إذا كانت كل القيم سالبة، فلن تكون أيٌّ منها أكبر من 0، لذا فإن القيمة العظمى التي تبدأ عند 0 لا تتغير أبدًا، وتُرجع الدالة 0. العنصر الأول مرشح حقيقي دائمًا، لذا فإن البدء به صحيح لأي قائمة. ويصلح أيضًا أصغر عدد صحيح في لغتك، ما دامت القائمة غير فارغة أبدًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def findMax(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [3, 17, 4, 12, 9]
الإخراج المتوقع
17