Contains Duplicate
لديك مصفوفة من الأعداد الصحيحة nums. أعد true إذا ظهرت قيمة ما فيها مرتين على الأقل، وfalse إذا كانت جميع القيم مختلفة.
الدالة
- numsinteger-array
- الأعداد الصحيحة المطلوب التحقق منها
- تُرجعboolean
- true إذا ظهرت قيمة ما مرتين على الأقل، وfalse خلاف ذلك
القيود
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109
أمثلة
- المدخلات
- nums = [3, 1, 4, 1, 5]
- المخرجات
- true
- الشرح
- تظهر القيمة
1عند الفهرس 1 ومرة أخرى عند الفهرس 3، لذا تكون الإجابةtrue.
- المدخلات
- nums = [2, 7, 1, 8]
- المخرجات
- false
- الشرح
2و7و1و8هي أربع قيم مختلفة، لذا لا يتكرر أيٌّ منها.
- المدخلات
- nums = [-4, 4, 0]
- المخرجات
- false
- الشرح
- لـ
-4و4القيمة المطلقة نفسها، لكنهما عددان مختلفان، ويظهر0مرة واحدة، لذا فالإجابة هيfalse.
سؤال إضافي
هل يمكنك التوقف بمجرد أن تصادف أول قيمة مكررة، بدلًا من قراءة المصفوفة كاملة دائمًا؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تنجح مقارنة كل قيمة بكل قيمة أخرى، لكن مع
10^4قيمة، يتطلب ذلك نحو5 × 10^7مقارنة. ما الذي يمكنك تذكّره عن القيم التي مررت بها بالفعل؟التكرار يعني أن القيمة الحالية سبق أن صادفتها. وتجيب مجموعة التجزئة عن السؤال «هل سبق أن صادفت هذه القيمة؟» بمتوسط زمن ثابت.
مرّ على المصفوفة مرة واحدة باستخدام مجموعة فارغة. لكل قيمة، أعد
trueإذا كانت موجودة بالفعل في المجموعة؛ وإلا فأضِفها. إذا انتهت الحلقة، فهذا يعني أن جميع القيم كانت مختلفة.
الحل
التكرار هو قيمة سبق أن صادفتها، والعمل هنا هو الإجابة بسرعة عن السؤال «هل صادفت هذه من قبل؟». إن مقارنة كل زوج تجيب عن السؤال، لكن عندما تكون n = 10^4، يكون عدد المقارنات n(n-1)/2، أي نحو 5 × 10^7 مقارنة. يجعل الفرز القيم المتساوية متجاورة، وتجيب مجموعة التجزئة عن السؤال بمتوسط زمن O(1)، ما يتيح المرور على العناصر مرة واحدة.
رتّب، ثم قارن العناصر المتجاورة
الفكرة
في المصفوفة المرتبة، تكون القيم المتساوية متجاورة. تُرتَّب [3, 1, 4, 1, 5] لتصبح [1, 1, 3, 4, 5]، وعندها يصبح العددان 1 متجاورين. لذا، بعد الترتيب، لا تقارن إلا كل قيمة بالقيمة التي تسبقها مباشرةً: n-1 مقارنةً بدلًا من n(n-1)/2 مقارنةً اللازمة لتجربة كل زوج.
إذا لم يكن أي عنصرين متجاورين متساويين، فهذا يعني أنه لا توجد أي قيمتين متساويتين في أي موضع: فأي قيمة تقع بين نسختين من x في الترتيب التصاعدي يجب أن تكون أكبر من x أو مساوية له، وأصغر من x أو مساوية له، وبالتالي ستكون نسخة أخرى من x.
تكون كلفة الفرز هي المهيمنة، بزمن O(n log n). يتطلب فرز nums في مكانه عدم استخدام مصفوفة إضافية، لكنه يعيد ترتيب مدخلات المستدعي؛ وإذا لم يكن ذلك مسموحًا، فافرز نسخةً منها، ما يكلّف مساحة O(n).
الخوارزمية
- رتّب
numsترتيبًا تصاعديًا. - كرّر
iمن 1 إلى الفهرس الأخير. - إذا كان
nums[i]يساويnums[i-1]، فأعِدtrue. - بعد الحلقة، أعِد
false.
def containsDuplicate(nums):
nums.sort()
# After sorting, equal values sit next to each other.
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return Falseمرور واحد باستخدام مجموعة تجزئة
الفكرة
مرّ على المصفوفة مرة واحدة واحتفظ بكل قيمة تجاوزتها في مجموعة تجزئة. قبل إضافة قيمة، اسأل المجموعة عمّا إذا كانت موجودة فيها بالفعل. بالنسبة إلى [3, 1, 4, 1, 5]، تنمو المجموعة لتصبح {3, 1, 4}، وعندما تصل 1 الثانية تكون المجموعة تحتفظ بها بالفعل، لذا تُرجع true دون قراءة 5.
تحتفظ المجموعة دائمًا بالقيم التي تسبق الموضع الحالي تحديدًا، لذا فإن العثور على قيمة يعني أن القيمة الحالية ظهرت سابقًا، والوصول إلى النهاية دون العثور على قيمة يعني أن جميع القيم مختلفة.
يستغرق البحث في مجموعة التجزئة والإدراج فيها O(1) من الوقت في المتوسط، لذا تستغرق عملية المرور بأكملها O(n). لكن ذلك يتطلب ذاكرة: إذا لم يكن هناك تكرار، فستنتهي المجموعة وهي تحتفظ بجميع القيم n.
الخوارزمية
- أنشئ مجموعة تجزئة فارغة
seen. - لكل قيمة في
nums، إذا كانت موجودة فيseen، فأعِدtrue. - وإلا، فأضِفها إلى
seen. - بعد الحلقة، أَعِد
false.
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
أخطاء شائعة وحالات حدّية
المنطق بسيط، لذا تكمن الأخطاء في حدود الحلقات وما تقارنه.
- مقارنة كل زوج مع بدء الحلقة الداخلية عند
j = i. عندئذٍ تطابق كل قيمة نفسها، وتكون الإجابة دائمًاtrue. - مقارنة القيم المتجاورة من دون الترتيب أولًا. في
[9, 1, 2, 3, 9]لا يكون العددان9متجاورين. - بدء حلقة الجيران عند الفهرس 0 وقراءة
nums[-1]. ابدأ عند 1، وستُرجع المصفوفة التي تحتوي على قيمة واحدةfalseعلى نحو صحيح. - اعتبار القيم ذات القيمة المطلقة نفسها متساوية، مثلًا باستخدام تجزئة
abs(x). العددان-4و4مختلفان. - كتابة دالة مقارنة للترتيب في C تُرجع
x - y. هنا يبقى الفرق ضمن±2 × 10^9، وهو أقل من حدintالبالغ2^31-1 = 2147483647، لذا تصادف أن القيمة تتسع له؛ أما مع قيم قريبة من حدودintفستحدث مشكلة تجاوز السعة، ويكون الترتيب خاطئًا. أعد(x > y) - (x < y)بدلًا من ذلك.
أسئلة شائعة3
ما التعقيد الزمني لعملية التحقق من وجود عناصر مكررة؟
يعمل حل مجموعة التجزئة بزمن O(n) في المتوسط، ويستخدم مساحة إضافية O(n). يستغرق الفرز أولًا زمنًا قدره O(n log n) ولا يحتاج إلى مصفوفة إضافية إذا كان بإمكانك إعادة ترتيب المدخلات. تستغرق مقارنة كل زوج زمنًا قدره O(n²).
هل يمكنك حل مسألة اكتشاف العناصر المكررة دون مساحة إضافية؟
نعم، إذا كان مسموحًا لك بإعادة ترتيب المصفوفة: رتّبها في مكانها وقارن كل قيمة بالقيمة المجاورة لها. هذا يستبدل مجموعة O(n) بزمن O(n log n). من دون إعادة ترتيب ومن دون ذاكرة إضافية، يكون الخيار الوحيد المتبقي هو فحص الأزواج O(n²).
لماذا تجعل مجموعة التجزئة عملية التحقق سريعة؟
تخزّن مجموعة التجزئة القيم وفقًا لقيم التجزئة الخاصة بها، لذا فإن التحقق مما إذا كانت تحتوي على قيمة يستغرق وقتًا ثابتًا في المتوسط بدلًا من البحث فيها. يتطلب كل عنصر عملية بحث واحدة وعملية إدراج واحدة، ما يجعل المرور بأكمله خطيًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def containsDuplicate(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [3, 1, 4, 1, 5]
الإخراج المتوقع
true