Single Number
لديك قائمة nums يظهر فيها كل عنصر مرتين بالضبط، باستثناء عنصر واحد يظهر مرة واحدة فقط. أعد العنصر الذي يظهر مرة واحدة.
الدالة
- numsinteger-array
- قائمة يظهر فيها كل عنصر مرتين باستثناء عنصر واحد
- تُرجعinteger
- القيمة التي تظهر مرة واحدة فقط
القيود
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- تظهر كل قيمة مرتين بالضبط، باستثناء قيمة واحدة تظهر مرة واحدة.
أمثلة
- المدخلات
- nums = [8, 3, 8]
- المخرجات
- 3
- الشرح
- يظهر 8 مرتين ويظهر 3 مرة واحدة، لذا الإجابة هي 3.
- المدخلات
- nums = [5, -2, 7, 5, 7]
- المخرجات
- -2
- الشرح
- يظهر كلٌّ من 5 و7 مرتين، و-2 هي القيمة الوحيدة التي تظهر مرة واحدة. تُوجد الإجابة السالبة بالطريقة نفسها التي تُوجد بها الإجابة الموجبة.
- المدخلات
- nums = [42]
- المخرجات
- 42
- الشرح
- القائمة التي تحتوي على قيمة واحدة لا تضم أي أزواج، لذا تكون تلك القيمة هي الإجابة.
+13 اختبارات مخفية عند الإرسال
سؤال إضافي
ماذا لو ظهرت كل قيمة ثلاث مرات باستثناء قيمة واحدة؟ لن تعود XOR وحدها تلغي الثلاثيات. هل لا يزال بإمكانك إيجاد القيمة الوحيدة في زمن O(n) وباستخدام ذاكرة إضافية مقدارها O(1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
إذا أمكن جعل كل زوج من القيم المتساوية يختفي، فلن يتبقى سوى الإجابة. هل توجد عملية تحوّل عددين متساويين إلى لا شيء؟
تُجري XOR ما يلي:
x ^ xيساوي0وx ^ 0يساويx. كما أنها لا تعتمد على الترتيب، لذا لا يلزم أن تكون نسختا القيمة متجاورتين حتى تُلغيا إحداهما الأخرى.احتفظ بمتغير واحد يبدأ بالقيمة
0. أجرِ عملية XOR على كل قيمة منnumsمعه، ثم أعده. لا حاجة إلى خريطة أو ترتيب.
الحل
العثور على القيمة الوحيدة التي ليس لها نظير هو مسألة عدّ، وتُحصي خريطة التجزئة كل قيمة في مرور واحد. لكن المشكلة تكمن في الذاكرة: إذ تكبر الخريطة مع القائمة. تلغي XOR الحاجة إلى العدّ تمامًا، لأن إجراء XOR لقيمة مع نفسها يعطي 0. أجرِ XOR على القائمة بأكملها، وستلغي كلّ قيمة نظيرتها، لتتبقى القيمة الوحيدة في مرور واحد باستخدام متغير واحد.
احسب كل قيمة عن طريق المسح
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
تناول كل قيمة بالتتابع وامسح القائمة بأكملها لعدّ عدد مرات ظهورها. تُحسب القيمة التي تنتمي إلى زوج مرتين. أما القيمة المفردة فتُحسب مرة واحدة، لذا أعد أول قيمة يكون عدد مرات ظهورها 1.
هذا صحيح لأن الأعداد تتبع مباشرةً تعريف الإجابة، ولا يتطلب الأمر ذاكرة إضافية تتجاوز عدّادًا.
هذا بطيء لأن كل واحدة من القيم n تؤدي إلى مسح كامل لـ n قيمة. عندما تكون القيمة المفردة في نهاية قائمة تضم 9,999 عنصرًا، يكون ذلك قريبًا من 10^8 مقارنة.
الخوارزمية
- كرّر على كل قيمة في
nums. - افحص القائمة كاملةً وعدّ القيم التي تساويها.
- إذا كان العدد 1، فأعِد تلك القيمة.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0عُدّ باستخدام خريطة تجزئة
الفكرة
إعادة فحص القائمة لكل قيمة تكرر العمل. بدلًا من ذلك، احسب جميع القيم في مرور واحد: خريطة تجزئة تربط كل قيمة بعدد مرات ظهورها، حيث تزيد كل خطوة عدد مرات ظهور القيمة الحالية بمقدار 1.
بالنسبة إلى [5, -2, 7, 5, 7]، تصبح الخريطة في النهاية: 5 → 2، -2 → 1، 7 → 2. يكشف مرور ثانٍ على الخريطة عن العنصر الذي عدد مرات ظهوره 1، وهو -2.
تتطلب كل قيمة تحديثًا واحدًا للخريطة، لذا يكون الزمن O(n). تحتوي الخريطة على نحو n/2 من العناصر، ما يعني استخدام ذاكرة إضافية قدرها O(n). في C، التي لا تحتوي على خريطة مدمجة، تؤدي مصفوفة من العدادات مفهرسة بواسطة value + 10^4 الدور نفسه لأن القيم صغيرة.
الخوارزمية
- أنشئ خريطة فارغة تربط كل قيمة بعدد مرات ظهورها.
- لكل قيمة في
nums، أضف 1 إلى عدد مرات ظهورها. - تصفّح الخريطة وأعِد القيمة التي يظهر عدد مرات ظهورها 1.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0طبّق XOR على جميع القيم
الفكرة
تقارن عملية XOR عددين بتًا بتًا، وتضبط البت عندما يختلفان. وينتج عن ذلك ثلاث حقائق: x ^ x = 0، وx ^ 0 = x، ولا يهم ترتيب العمليات.
لذا طبّق XOR على القائمة كلها في متغير واحد يبدأ بقيمة 0. يمكنك إعادة تجميع العمليات بحيث يلتقي كل زوج بنظيره، وتصبح قيمة كل زوج 0. وما يتبقى هو 0 ^ single، أي القيمة الوحيدة. بالنسبة إلى [8, 3, 8]: 0 ^ 8 = 8، ثم 8 ^ 3 = 11، ثم 11 ^ 8 = 3.
تعمل هذه الطريقة مع الأعداد السالبة أيضًا. تعمل XOR على بتات تمثيل المتمم الثنائي، ولذا فإن عددين سالبين متساويين لهما البتات نفسها، فيلغي أحدهما الآخر مثل أي زوج آخر. تقرأ الحلقة كل قيمة مرة واحدة وتحتفظ بمتغير واحد: زمن O(n) وذاكرة إضافية O(1).
الخوارزمية
- عيّن
resultإلى 0. - لكل قيمة في
nums، عيّنresultإلىresult ^ value. - أعِد
result.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
أخطاء شائعة وحالات حدّية
حلقة XOR قصيرة، لذا تكمن الأخطاء في نقطة بدايتها والبدائل التي يلجأ إليها الناس.
- بدء
resultعندnums[0]ثم المرور على كل قيمة، بما فيها الفهرس 0. تُضاف القيمة الأولى بعملية XOR مرتين، فتلغي نفسها. ابدأ من 0، أو تخطَّ الفهرس 0. - الترتيب ومقارنة العناصر المتجاورة بخطوات مقدارها اثنان، ثم نسيان أن القيمة الوحيدة قد تكون العنصر الأخير. في
[1, 1, 2]لا يوجد زوج غير متطابق، والإجابة هي القيمة المتبقية 2. - استخدام
2 × sum(distinct values) - sum(nums). يعطي العدد الصحيح، لكن مجموعة القيم المميزة تستهلك ذاكرةO(n)، وهو ما تتجنبه طريقة XOR. - توقّع أن تعمل XOR مع أعداد تكرار أخرى. فهي تلغي القيم التي تظهر عددًا زوجيًا من المرات. إذا ظهرت قيمة ثلاث مرات، فستبقى نسخة واحدة وتفسد الإجابة.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة العدد الوحيد؟
يعمل حل XOR في زمن O(n) ويستخدم مساحة إضافية O(1)، لأنه يقرأ كل قيمة مرة واحدة ويحتفظ بمتغير واحد. كما تعمل خريطة التجزئة في زمن O(n)، لكنها تحتاج إلى ذاكرة O(n). أما عدّ كل قيمة بمسح جديد فيستغرق O(n²).
لماذا يحل XOR مسألة الرقم المفرد؟
إن إجراء XOR لعدد مع نفسه يعطي 0، وإجراء XOR مع 0 لا يغيّر شيئًا، كما أن ترتيب العمليات لا يهم. لذلك، عند إجراء XOR على القائمة كلها، يمكن تجميع كل زوج معًا فيلغي أحدهما الآخر إلى 0. ولا يتبقى سوى القيمة التي ليس لها شريك.
هل تنجح حيلة XOR مع الأعداد السالبة؟
نعم. تعمل XOR على البِتّات التي تخزّن العدد، وتُخزَّن الأعداد السالبة بتمثيل المتمّم الثنائي. للأعداد السالبة المتساوية بِتّات متطابقة، لذا تُلغي بعضها بعضًا تمامًا مثل الأعداد الموجبة. في [5, -2, 7, 5, 7] تكون النتيجة -2.
كيف تحلّها عندما تظهر القيم الأخرى ثلاث مرات؟
تلغي XOR الأزواج، لا الثلاثيات، لذا فهي تفشل في هذه الحالة. بدلًا من ذلك، احسب عدد القيم التي يحتوي كلٌّ منها على كل بت من البتات الـ32. لكل بت، يكون باقي قسمة هذا العدد على 3 هو البت المقابل في القيمة الوحيدة، لأن الثلاثيات تضيف مضاعفات العدد 3. يظل هذا التنفيذ يستغرق زمنًا O(n) ويستخدم ذاكرة إضافية O(1).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def singleNumber(nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [8, 3, 8]
المتوقع
3