Intersection of Two Arrays
لديك مصفوفتان من الأعداد الصحيحة، nums1 وnums2. أعد كل قيمة تظهر في المصفوفتين، مرتبة ترتيبًا تصاعديًا. تظهر كل قيمة مشتركة في الإجابة مرة واحدة، مهما تكرر ظهورها في أي من المصفوفتين.
الدالة
- nums1integer-array
- القائمة الأولى من الأعداد الصحيحة
- nums2integer-array
- القائمة الثانية من الأعداد الصحيحة
- تُرجعinteger-array
- القيم الموجودة في كلتا القائمتين، مرة واحدة لكل قيمة، بترتيب تصاعدي
القيود
1 ≤ nums1.length, nums2.length ≤ 5000-105 ≤ nums1[i], nums2[i] ≤ 105- تظهر قيمة واحدة على الأقل في كلتا المصفوفتين.
أمثلة
- المدخلات
- nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
- المخرجات
- [4, 6]
- الشرح
- يوجد
4و6في كلتا المصفوفتين. يظهر4مرتين فيnums2لكنه مدرج مرة واحدة، ولا يظهر2و9مطلقًا فيnums2.
- المدخلات
- nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
- المخرجات
- [-3, 7]
- الشرح
- العدد
-3والعدد7موجودان في كلتا المصفوفتين. عند الترتيب تصاعديًا، يأتي-3أولًا، رغم أن7يأتي أولًا فيnums2.
+16 اختبارات مخفية عند الإرسال
سؤال إضافي
ماذا لو كانت nums1 تحتوي على 10 قيم، وكانت nums2 تحتوي على مليون قيمة، مرتبة مسبقًا؟ أي نهج ستختار، وهل يمكن للبحث الثنائي أن يتفوق على المرور الكامل؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
لكل قيمة في
nums1، يمكنك فحص جميع عناصرnums2. مع وجود 5000 قيمة في كل مصفوفة، قد يصل ذلك إلى2.5 × 10^7مقارنة. ما السؤال الذي تطرحه مرارًا وتكرارًا؟السؤال المتكرر هو: "هل هذه القيمة موجودة في المصفوفة الأخرى؟". وتجيب مجموعة تجزئة مُنشأة من إحدى المصفوفتين عن هذا السؤال في زمن ثابت في المتوسط.
أنشئ مجموعة من
nums1. مرّ علىnums2؛ عندما تكون قيمة ما في المجموعة، أضفها إلى الإجابة وأزلها من المجموعة، حتى لا تُضاف نسخة لاحقة منها مرة أخرى. رتّب الإجابة قبل إرجاعها.
الحل
هناك تفصيلان يحددان حل هذه المسألة: القيمة التي تتكرر في كلا الجانبين تُضاف إلى الإجابة مرة واحدة، ويجب أن تكون الإجابة مرتبة. تنجح مقارنة كل زوج، لكنها تتطلب n × m مقارنة، أي 2.5 × 10^7 عندما تحتوي كلتا المصفوفتين على 5000 قيمة. يتيح ترتيب المصفوفتين لمؤشرين الوصول إلى القيم المشتركة بالترتيب، وتُجيب مجموعة تجزئة لإحدى المصفوفتين عن سؤال «هل هذه القيمة موجودة في nums1؟» في زمن ثابت.
قارن كل زوج
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
خذ كل قيمة من nums1 وابحث عنها في nums2. أوقف البحث عند أول تطابق، وتجاوز أي قيمة موجودة بالفعل في الإجابة، لذا فإن مقارنة [8, 8, 8, 8] مع [8, 8] تعطي قيمة 8 واحدة، لا أربعًا. رتّب الإجابة في النهاية.
هذا صحيح لأن القيمة تُضاف إلى الإجابة بالضبط عندما تجد نسخة منها في nums1 تطابقًا في nums2، والتجاوز يمنع إضافتها مرتين.
هذه الطريقة بطيئة لأن كل قيمة في nums1 قد تبحث في nums2 بأكمله. مع وجود 5000 قيمة في كل مصفوفة، قد يصل عدد المقارنات إلى 2.5 × 10^7، وفي الاختبارات الكبيرة لا تجد معظم القيم تطابقًا، لذا يستمر معظم البحث حتى النهاية.
الخوارزمية
- ابدأ بقائمة إجابات فارغة.
- لكل قيمة
aفيnums1، تخطَّها إذا كانت موجودة بالفعل في الإجابة. - وإلا، افحص
nums2؛ عند أول قيمة تساويa، أضفaإلى الإجابة وأوقف الفحص. - رتّب الإجابة ترتيبًا تصاعديًا وأعِدها.
def intersection(nums1, nums2):
result = []
for a in nums1:
if a in result:
continue
# Look for a anywhere in nums2.
for b in nums2:
if a == b:
result.append(a)
break
result.sort()
return resultرتّب كليهما، ثم تقدّم باستخدام مؤشّرين
الفكرة
بعد الترتيب، يصبح المثال 1 [2, 2, 4, 6, 9] و[1, 4, 4, 6]. ضع المؤشر i عند بداية المصفوفة الأولى وj عند بداية الثانية. يتحرك المؤشر الموجود عند القيمة الأصغر إلى الأمام: فلا يمكن لتلك القيمة أن تطابق أي قيمة أبعد في المصفوفة الأخرى، حيث تكون كل قيمة مساوية لها أو أكبر منها. عندما يرى المؤشران القيمة نفسها، تكون مشتركة، لذا أضفها وحرّك كليهما.
في المثال: تؤدي 2 > 1 إلى تحريك j، وتكون كلتا 2 أصغر من 4، لذا يتحرك i، وتضيف 4 = 4 القيمة 4، وتكون قيمة 4 الثانية أصغر من 6، لذا يتحرك j، وتضيف 6 = 6 القيمة 6. إذا تكررت قيمة مشتركة عدة مرات في كلا الجانبين، مثل 2 في [2, 2, 3] و[2, 2]، فإنها تتطابق أكثر من مرة؛ ومقارنتها بآخر قيمة أُضيفت تُبقي نسخة واحدة. وتكون النتيجة مرتبة دون الحاجة إلى خطوة إضافية.
يستغرق الترتيب O(n log n + m log m)، ويستغرق المرور O(n + m) لأن كل خطوة تحرّك مؤشرًا واحدًا على الأقل. ترتّب معظم الإصدارات نُسخًا، ما يستهلك O(n + m) من الذاكرة. إذا كان بإمكانك إعادة ترتيب المدخلات، فرتّبها في مكانها، كما يفعل كود C، وعندها تكون الإجابة هي الذاكرة الإضافية الوحيدة.
الخوارزمية
- رتّب كلتا المصفوفتين.
- عيّن
i = 0وj = 0. - ما دام كلا المؤشّرين داخل مصفوفتَيهما، حرّك المؤشّر عند القيمة الأصغر.
- عند تساوي القيم، أضف القيمة ما لم تكن مساوية لآخر قيمة أُضيفت، ثم حرّك كلا المؤشّرين.
- أعِد الإجابة.
def intersection(nums1, nums2):
a = sorted(nums1)
b = sorted(nums2)
i, j = 0, 0
result = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
i += 1
elif a[i] > b[j]:
j += 1
else:
# A shared value: keep it once, even if it repeats.
if not result or result[-1] != a[i]:
result.append(a[i])
i += 1
j += 1
return resultمجموعة التجزئة للمصفوفة الأولى
الفكرة
ضع كل قيمة من nums1 في مجموعة تجزئة. في المثال 1، تكون المجموعة {6, 2, 9, 4}: تتلاشى النسخة المكررة من 2 عند إضافتها. ثم مرّ على nums2 واسأل المجموعة عن كل قيمة بزمن ثابت. القيمة الأولى 4 موجودة، لذا تُضاف إلى الإجابة. أما القيمة الثانية 4 فلا ينبغي إضافتها، لذا أزِل قيمة من المجموعة لحظة تطابقها. القيمة 1 غير موجودة، بينما 6 موجودة، وهذا يعطينا [4, 6].
إزالة القيمة عند التطابق هي ما يضمن ظهور كل قيمة مرة واحدة: فبعد أول تطابق لها، تختفي القيمة من المجموعة، لذا لن تجد النسخ اللاحقة في nums2 شيئًا. كل قيمة أُضيفت موجودة في المصفوفتين، وكل قيمة مشتركة تُضاف عند وصول نسختها الأولى في nums2.
يستغرق إنشاء المجموعة والمرور عليها O(n + m) في المتوسط. تظهر الإجابة بترتيب nums2، لذا رتّبها في النهاية؛ فهي تحتوي على k ≤ min(n, m) من القيم، ما يستغرق O(k log k). لا تحتوي C على مجموعة مضمّنة، لذا يستخدم كود C مصفوفة علامات مفهرسة باستخدام value + 10^5، وهذا ينجح لأن القيم محدودة.
الخوارزمية
- أنشئ مجموعة تجزئة
firstمنnums1. - لكل قيمة في
nums2، إذا كانت موجودة فيfirst، فأضِفها إلى الإجابة واحذفها منfirst. - رتّب الإجابة بترتيب تصاعدي.
- أعِدها.
def intersection(nums1, nums2):
first = set(nums1)
result = []
for num in nums2:
if num in first:
result.append(num)
# Remove it so a repeat in nums2 is not added twice.
first.remove(num)
result.sort()
return result
أخطاء شائعة وحالات حدّية
تأتي معظم الإجابات الخاطئة هنا من القيم المكررة ومن ترتيب الناتج.
- إضافة قيمة في كل مرة تتطابق فيها. تتشارك
[2, 2, 3, 3, 3]و[3, 2, 2]قيمتين، لذا فالإجابة هي[2, 3]، وليست[3, 2, 2]. - إرجاع القيم بالترتيب الذي عثرت عليها به. تتبع عملية المرور على مجموعة التجزئة
nums2، لذا يجب مع ذلك ترتيب[7, -3]ليصبح[-3, 7]. - ترتيب الأعداد على أنها نصوص. تقارن JavaScript السلاسل النصية عند استخدام
sort()دون مقارن، لذا تبقى[100000, 99]بهذا الترتيب. مرّر(x, y) => x - y. - استخدام تقاطع المجموعات ونسيان الترتيب. تعثر
set(nums1) & set(nums2)في Python على القيم الصحيحة دون ترتيب محدد؛ لذا أحيطها بـsorted. - فهرسة مصفوفة علامات باستخدام القيمة الخام.
-3ليس فهرسًا صالحًا؛ أزِح كل قيمة بمقدار10^5أولًا.
أسئلة شائعة4
ما هو التعقيد الزمني لتقاطع مصفوفتين؟
باستخدام مجموعة تجزئة، يستغرق العثور على القيم المشتركة O(n + m) في المتوسط، وتضيف عملية فرز قيم الإجابة البالغ عددها k مقدار O(k log k)؛ وتستخدم المجموعة مساحة O(n). يستغرق فرز المصفوفتين واجتيازهما باستخدام مؤشرين O(n log n + m log m). تستغرق مقارنة كل زوج O(n × m).
هل ينبغي أن تستخدم مجموعة تجزئة أم مؤشرين؟
استخدم مجموعة التجزئة عندما تكون المصفوفتان غير مرتبتين وتتوفر ذاكرة: فهي تتطلب أقل قدر من العمل. استخدم مؤشرين عندما تكون المصفوفتان مرتبتين بالفعل، أو عندما تكون الذاكرة محدودة ويمكنك ترتيبهما في مكانهما. لا يحتاج المرور إلى مجموعة، وينتج الإجابة بالترتيب.
كيف تحتفظ بالقيم المتكررة في التقاطع؟
إذا كان ينبغي أن تظهر قيمة بعدد مرات ظهورها في كلا المصفوفتين، بحيث تعطي [3, 1, 3, 3] و[3, 3] النتيجة [3, 3]، فاستبدل المجموعة بخريطة للعدّ. احسب مرات ظهور قيم nums1، ولكل قيمة في nums2 يكون عدد مرات ظهورها أكبر من صفر، أضفها وخفّض عدد مرات ظهورها. في المرور باستخدام مؤشرين، احذف التحقق من آخر قيمة أُضيفت.
كيف تجد التقاطع عندما تكون إحدى المصفوفتين أكبر من أن تتسع في الذاكرة؟
أنشئ مجموعة التجزئة من المصفوفة التي تتسع في الذاكرة، واقرأ المصفوفة الكبيرة على أجزاء، مع التحقق من كل قيمة مقابل المجموعة وإزالتها عند العثور على تطابق. تظل الذاكرة المستخدمة بحجم المصفوفة الأصغر. إذا لم تتسع أي من المصفوفتين، فرتّبهما على القرص ونفّذ المرور باستخدام مؤشرين على الملفين المرتبين.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def intersection(nums1, nums2):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
nums1 = [6, 2, 9, 2, 4] nums2 = [4, 4, 1, 6]
المتوقع
[4, 6]