Count Even Numbers
ب given قائمة غير فارغة من الأعداد الصحيحة nums، أعد عدد القيم الزوجية فيها. يكون العدد زوجيًا عندما لا يترك قسمته على 2 أي باقٍ، ويشمل ذلك 0 والأعداد السالبة مثل -4.
الدالة
- numsinteger-array
- قائمة الأعداد الصحيحة المطلوب التحقق منها
- تُرجعinteger
- عدد القيم الزوجية في nums
القيود
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
أمثلة
- المدخلات
- nums = [3, 8, 12, 5, 6]
- المخرجات
- 3
- الشرح
8و12و6تقبل القسمة على2دون باقٍ؛ أما3و5فلا. الإجابة هي3.
- المدخلات
- nums = [-4, -3, 0, 7]
- المخرجات
- 2
- الشرح
-4 = 2 × (-2)و0 = 2 × 0، لذا فكلاهما زوجي.-3و7فرديان، والعدد هو2.
- المدخلات
- nums = [1, 9, 15]
- المخرجات
- 0
- الشرح
1و9و15كلها أعداد فردية، لذا الإجابة هي0.
سؤال إضافي
تتلقى أسئلة كثيرة: كم عدد القيم الزوجية الواقعة بين الفهرس l والفهرس r؟ بعد المرور مرة واحدة على nums، هل يمكنك الإجابة عن كل سؤال في زمن O(1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ما المتبقي عند قسمة عدد زوجي على
2؟تكون القيمة
xزوجية إذا وفقط إذا كانتx % 2تساوي0. انتبه: بالنسبة إلى عدد فردي سالب، تعطي بعض اللغات-1كباقٍ، وليس1.ابدأ عدّادًا عند
0، واقرأ كل قيمة مرة واحدة، وأضف1كلما كان باقي القسمة على2هو0.
الحل
تحقّق من كل قيمة مرة واحدة، وعُدّ القيم التي يكون باقي قسمتها على 2 هو 0. مقارنة الباقي بـ 0، بدلًا من اختبار ما إذا كان العدد فرديًا بمقارنته بـ 1، تضمن التعامل الصحيح مع الأعداد السالبة.
اجمع القيم الزوجية، ثم عُدّها
الفكرة
استخرج القيم الزوجية باستخدام التصفية، ثم أعد طول الناتج. بالنسبة إلى [3, 8, 12, 5, 6]، تكون القائمة المُصفّاة [8, 12, 6]، لذا فالإجابة هي 3.
التعقيد الزمني هو O(n)، لكن القائمة الجديدة تستهلك ذاكرة بمقدار O(n)، لما يصل إلى 5000 قيمة، فقط لقراءة طولها مرة واحدة.
الخوارزمية
- أنشئ قائمة جديدة تحتوي على كل
xفيnumsبحيث يكونx % 2 == 0. - أعِد طول تلك القائمة.
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)عُدّ باستخدام عدّاد متزايد
الفكرة
استخدم عدّادًا بدلًا من قائمة، وأضف 1 لكل قيمة تحقق x % 2 == 0. يكون باقي قسمة العدد الزوجي 0 مهما كانت إشارته، لذا يصح الاختبار مع -4 و0 في كل لغة. أما اختبار الفردي المكتوب x % 2 == 1 فلا يصح: ففي C وJava وJavaScript ومعظم اللغات الشبيهة بـ C، يأخذ باقي القسمة إشارة العدد، لذا فإن -3 % 2 يساوي -1.
مرور واحد وعدد صحيح واحد: زمن O(n) ومساحة O(1).
الخوارزمية
- عيّن
countإلى0. - كرّر على كل قيمة
xفيnums. - إذا كان
x % 2 == 0، فأضف1إلىcount. - بعد الحلقة، أَعِد
count.
def countEvens(nums):
count = 0
for x in nums:
if x % 2 == 0: # 0 also works for negatives, where the remainder can be -1
count += 1
return count
أخطاء شائعة وحالات حدّية
- عدّ القيم الفردية باستخدام
x % 2 == 1وطرحها من الطول. في اللغات الشبيهة بـ C، تكون نتيجة-3 % 2هي-1، لذا تُرجع[-3]القيمة 1 بدلًا من 0. - اعتبار
0ليس زوجيًا ولا فرديًا.0 = 2 × 0، لذا تُرجع[0]القيمة1. - كتابة اختبار البتات بالشكل
x & 1 == 0. في C وC++ وJavaScript، تكون أسبقية==أعلى من أسبقية&، لذا يعني ذلكx & (1 == 0)، وتكون نتيجته دائمًا0، فلا يُحصي أي شيء. اكتب(x & 1) == 0.
أسئلة شائعة3
كيف تتحقق برمجيًا مما إذا كان العدد زوجيًا؟
اختبر ما إذا كان الباقي بعد القسمة على 2 يساوي صفرًا: x % 2 == 0. ينجح ذلك مع الأعداد الموجبة والسالبة والصفر، حتى في اللغات التي تكون فيها نتيجة -3 % 2 هي -1. يمكنك أيضًا فحص البت الأقل أهمية باستخدام (x & 1) == 0.
هل الصفر عدد زوجي؟
نعم. صفر مقسومًا على 2 يساوي 0 دون باقٍ، لذا ينطبق عليه تعريف العدد الزوجي. وهو يقع أيضًا بين العددين الفرديين -1 و1، حيث يقع العدد الزوجي.
ما هو التعقيد الزمني لعدّ الأعداد الزوجية في مصفوفة؟
تستغرق عملية مرور واحدة باستخدام عدّاد زمنًا قدره O(n) ومساحة إضافية قدرها O(1). يجب فحص كل قيمة، لذا لا توجد طريقة أسرع من O(n).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def countEvens(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [3, 8, 12, 5, 6]
الإخراج المتوقع
3