Find the Duplicate Number
لديك مصفوفة nums تحتوي على n+1 عددًا صحيحًا، كلٌّ منها بين 1 وn. تظهر قيمة واحدة بالضبط أكثر من مرة، وقد تظهر مرات عديدة، وتُعيد تلك القيمة.
حلّ المسألة دون تغيير nums وباستخدام مقدار ثابت فقط من الذاكرة الإضافية.
الدالة
- numsinteger-array
- n+1 عددًا صحيحًا، كلٌّ منها بين 1 و n
- تُرجعinteger
- القيمة التي تظهر أكثر من مرة
القيود
1 ≤ n ≤ 104nums.length == n+11 ≤ nums[i] ≤ n- تظهر قيمة واحدة بالضبط مرتين أو أكثر؛ وتظهر كل قيمة أخرى مرة واحدة على الأكثر.
أمثلة
- المدخلات
- nums = [2, 5, 1, 3, 5, 4]
- المخرجات
- 5
- الشرح
- هنا
nتساوي 5، والعدد 5 يقع في الموضعين 1 و4، لذا فالإجابة هي 5. وتظهر كل قيمة أخرى من 1 إلى 5 مرة واحدة.
- المدخلات
- nums = [4, 2, 4, 1, 4]
- المخرجات
- 4
- الشرح
- يظهر 4 ثلاث مرات، في المواضع 0 و2 و4، بينما لا يظهر 3 على الإطلاق. يمكن للتكرار أن يحل محل عدة قيم مفقودة، لذا فالإجابة هي 4.
سؤال إضافي
يحافظ البحث الثنائي على القيم على كلتا القاعدتين ضمن زمن O(n log n). هل يمكنك الحفاظ عليهما ضمن زمن O(n)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تقع كل قيمة بين 1 و
n، وللمصفوفة مواضع من 0 إلىn. لذا فإن كل قيمة هي أيضًا موضع صالح. ابدأ عند الموضع 0، وانتقل إلى الموضعnums[0]، ثم إلى الموضع الذي تشير إليه تلك القيمة، وهكذا. ماذا لا بد أن يحدث لهذا المسار؟لا يتوقف المسار أبدًا، ولا يملك سوى
n+1موضعًا لزيارته، لذا يدخل في حلقة. ويُوصَل إلى الموضع الذي يدخل عنده الحلقة من موضعين مختلفين، وكلاهما يحمل ذلك الموضع كقيمة له.اعثر على مدخل الحلقة باستخدام مؤشرين يبدأان من الموضع 0: يقفز أحدهما مرة واحدة في كل دورة، والآخر مرتين، حتى يصلا إلى الموضع نفسه. ثم أعد أحدهما إلى 0 وحرّك كليهما قفزة واحدة في كل مرة. سيلتقيان عند المدخل، وهو الإجابة.
الحل
تعثر مجموعة التجزئة أو عملية الفرز على القيمة المكررة فورًا، لكن كليهما يخالف القواعد: تحتاج المجموعة إلى ذاكرة لكل قيمة، كما أن الفرز يغيّر nums. يكمن الحل في الأرقام. كل قيمة تقع بين 1 وn، لذا فهي أيضًا موضع صالح في المصفوفة. اقرأ كل قيمة على أنها رابط إلى موضع آخر، وسيؤدي تتبّع الروابط بدءًا من الموضع 0 دائمًا إلى حلقة تكون نقطة الدخول إليها هي القيمة المكررة. يعثر مؤشرا فلويد السريع والبطيء على نقطة الدخول هذه باستخدام عددين صحيحين.
قارن كل زوج
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
تقع القيمة المكررة في موضعين i < j على الأقل. قارن كل موضع بكل موضع يليه؛ فالزوج الأول الذي يحتوي على قيم متساوية يعطي الإجابة. في المثال الأول، يحتوي الموضع 1 على 5، ويعثر الفحص بدءًا من الموضع 2 فصاعدًا على 5 أخرى في الموضع 4.
هذا يحافظ على القاعدتين: لا تتم كتابة أي شيء، والذاكرة الوحيدة هي عدّادا حلقتين. وهو بطيء لأنه يقارن بين الأزواج. مع n+1 = 10,001 قيمة، ووجود النسختين قرب النهاية، يفحص نحو 5 × 10^7 زوجًا.
الخوارزمية
- لكل موضع
iمن 0 حتى النهاية: - لكل موضع
jبعدi، قارنnums[i]بـnums[j]. - أعِد
nums[i]عند أول تطابق.
def findDuplicate(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return nums[i]
return -1 # unreachable: the input always holds a repeatالبحث الثنائي عن القيمة
الفكرة
ابحث في نطاق القيم، لا في المواضع. اختر حدًا فاصلًا m واحسب عدد عناصر nums التي تقل عن m أو تساويه.
إذا كان التكرار d أكبر من m، فستظهر كل قيمة من 1 إلى m مرة واحدة على الأكثر، لذا لن يتجاوز العدد m. أما إذا كان d أقل من m أو يساويه، فستظهر كل قيمة أكبر من m مرة واحدة على الأكثر، لذا لن يزيد عدد العناصر الأكبر من m على n-m، وسيكون عدد العناصر الأقل من m أو المساوية له m+1 على الأقل. لذلك يكون الاختبار "count > m" خطأ لكل m أقل من d، وصحيحًا ابتداءً من d. يعثر البحث الثنائي على أول m تصبح عنده النتيجة صحيحة، وهو d.
في المثال الثاني، قيمة n هي 4. عندما تكون m = 2، يعطي العنصران 2 و1 عددًا يساوي 2، وليس أكثر من 2، لذا فالجواب أكبر من 2. وعندما تكون m = 3، يظل العدد 2، لذا فالجواب هو 4. تقرأ كل جولة المصفوفة كاملة مرة واحدة وتُنصّف النطاق، لذا يكون العمل O(n log n): نحو 14 مرورًا على 10,001 قيمة.
الخوارزمية
- عيّن
low= 1 وhigh=n، أي طولnumsناقص واحد. - ما دام
low < high، خذmidفي منتصف المسافة بينهما. - احسب عدد عناصر
numsالتي قيمتها لا تتجاوزmid. - إذا كان العدد أكبر من
mid، فعيّنhigh=mid؛ وإلا فعيّنlow=mid+1. - أعِد
low.
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
# How many values fall in 1..mid?
count = 0
for x in nums:
if x <= mid:
count += 1
if count > mid:
high = mid # 1..mid holds more values than it has room for
else:
low = mid + 1 # the repeat is above mid
return lowاكتشاف دورة فلويد في روابط القيم
الفكرة
اقرأ المصفوفة كروابط: الموضع i يشير إلى الموضع nums[i]. لكل موضع من 0 إلى n رابط صادر واحد بالضبط، وكل رابط يصل إلى موضع ما بين 1 وn. في المثال الأول، الروابط هي 0 → 2، 1 → 5، 2 → 1، 3 → 3، 4 → 5 و5 → 4.
ابدأ من الموضع 0 واتبع الروابط. لا يمكن للمسار أن يتوقف أبدًا، لأن لكل موضع رابطًا، ولأن عدد المواضع هو n+1 فقط، فلا بد أن يعود إلى موضع سبق أن مرّ به. ومنذ تلك اللحظة، يدور إلى ما لا نهاية. يتكوّن المسار من ذيل يتبعه حلقة، ويشبه الحرف ρ. في المثال الأول، يكون المسار 0، 2، 1، 5، 4، 5، 4، وهكذا: الذيل هو 0، 2، 1 والحلقة هي 5، 4. يشير الموضع 3 إلى نفسه، لكن المسار لا يصل إليه، ولا يسبب ذلك أي مشكلة.
مدخل الحلقة هو القيمة المكررة. يدخل المسار إلى 5 مرتين من موضعين مختلفين: مرة من نهاية الذيل (الموضع 1، لأن nums[1] يساوي 5) ومرة من نهاية الحلقة (الموضع 4، لأن nums[4] يساوي 5). يحمل موضعان مختلفان القيمة 5، لذا تتكرر 5. يحتوي الذيل دائمًا على الموضع 0، لأن أي قيمة لا تساوي 0 ولا يشير أي رابط إليه، لذا يكون للمدخل دائمًا هذان المساران المختلفان للوصول إليه. تتكرر قيمة واحدة بالضبط، لذا فإن المدخل هو تلك القيمة.
والآن اعثر على المدخل باستخدام مؤشرين، كما في اكتشاف الدورة في القائمة المرتبطة. في المرحلة 1، يتبع slow رابطًا واحدًا في كل خطوة، ويتبع fast رابطين، حتى يقفا عند الموضع نفسه في مكان ما داخل الحلقة. في المثال الأول، يلتقيان عند 4. في المرحلة 2، أعد slow إلى 0، واترك fast في مكانه، ثم حرّك كليهما رابطًا واحدًا في كل خطوة. سيلتقيان عند المدخل.
لماذا تنجح المرحلة 2: لنفترض أن الذيل يتطلب T رابطًا للوصول إلى المدخل، وأن الحلقة تضم C موضعًا. عندما التقى المؤشران، كان slow قد قطع s خطوة، وقطع fast 2s خطوة. كان كلاهما في الموضع نفسه، لذا فإن خطوات s الإضافية التي قطعها fast كانت عددًا صحيحًا من الدورات حول الحلقة. بعد T خطوة أخرى، يصل slow إلى المدخل انطلاقًا من 0، ويكون fast في الموضع الذي يصل إليه المسار من 0 بعد s+T خطوة، لأن دوراته الإضافية لا تغيّر شيئًا. أي إنه قطع T خطوة للوصول إلى المدخل، بالإضافة إلى s خطوة تمثل عددًا صحيحًا من الدورات، وهذا يضعه عند المدخل أيضًا. لا يمكن أن يلتقيا قبل ذلك، لأن slow لا يزال على الذيل، بينما لا يغادر fast الحلقة أبدًا. في المثال الأول، يتحرك slow عبر 2، 1، 5، بينما يتحرك fast عبر 5، 4، 5، ويلتقيان عند 5 بعد T = 3 خطوات.
تستغرق كل مرحلة O(n) خطوة، والذاكرة الوحيدة المستخدمة هي موضعان، ولا تُعدّل nums أبدًا.
الخوارزمية
- اعتبر كل موضع
iعقدةً تشير إلى الموضعnums[i]، وابدأ كلا المؤشرين من الموضع 0. - المرحلة 1: حرّك
slowإلىnums[slow]وfastإلىnums[nums[fast]]حتى يتساويا. - المرحلة 2: أعد
slowإلى 0. - حرّك كليهما رابطًا واحدًا في كل مرة،
slowإلىnums[slow]وfastإلىnums[fast]، حتى يتساويا. - أعِد ذلك الموضع: فهو القيمة المكررة.
def findDuplicate(nums):
# Treat each index i as a node with one link, to nums[i].
# Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: restart one pointer at index 0 and move both one link at a time.
# They meet at the cycle's entrance, the index two positions link to.
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
أخطاء شائعة وحالات حدّية
تنتج معظم الإجابات الخاطئة عن الخلط بين المواضع والقيم، أو عن التوقف قبل إكمال إحدى مراحل طريقة Floyd.
- إرجاع نقطة الالتقاء في المرحلة الأولى. فهي موضع ما على الحلقة، وليس بالضرورة مدخلها. في المثال الأول، يلتقي المؤشران عند الموضع 4، لكن الإجابة هي 5.
- التحقق من
slow == fastقبل الحركة الأولى. فكلاهما يبدأ عند الموضع 0، لذا تنتهي الحلقة فورًا. تحرّك أولًا ثم قارن، أو ابدأ بهما متقدمين بمقدار وصلة واحدة ووصلة اثنتين. - بدء السير من أي موضع غير الموضع 0. فلا توجد وصلة تشير إلى الموضع 0، إذ لا توجد أي قيمة تساوي 0، وهذا ما يضمن وجود ذيل. قد يؤدي البدء من موضع آخر إلى وضعك على حلقة لا سبيل للوصول إليها من الخارج، مثل الموضع 3 في المثال الأول، ومدخلها لا يثبت شيئًا.
- افتراض أن القيمة المكررة تظهر مرتين بالضبط. تعطي حيلة الجمع، أي المجموع ناقص
1 + 2 + ... + n، الناتج 15 ناقص 10 = 5 في المثال الثاني، لكن الإجابة هي 4. وينطبق الأمر نفسه على حيل XOR. - إجراء البحث الثنائي على المواضع بدلًا من القيم، أو اختبار
count >= mid. يكون عدد القيم التي لا تتجاوزmمساويًا تمامًا لـmعندما لا تتكرر أي قيمة من 1 إلىmولا تكون أي منها مفقودة، لذا فإن>وحده هو ما يميّز بين الجانبين. - تحديد القيم التي زرتها بنفي
nums[x]أو بتبديل القيم إلى أماكنها. كلا الأسلوبين ينجح، لكن كليهما يغيّر المصفوفة، وهو ما تمنعه المهمة.
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة إيجاد العدد المكرر؟
يعمل اكتشاف الدورة باستخدام خوارزمية Floyd بزمن O(n) وبذاكرة إضافية O(1): تتبع كل مرحلة من مرحلتيها عددًا من الروابط لا يتجاوز بضعة أمثال n. يستغرق البحث الثنائي عن القيم زمنًا O(n log n) وذاكرة O(1). أما مقارنة كل زوج فتستغرق O(n²).
لماذا تعثر خوارزمية فلويد لاكتشاف الدورات على الرقم المكرر؟
إذا قرأت كل قيمة على أنها رابط من موضعها إلى الموضع الذي تشير إليه، فلا بد أن تنتهي المسيرة التي تبدأ من الموضع 0 في حلقة، لأنها لا تتوقف وليس أمامها سوى n+1 موضعًا لتذهب إليه. يصل المسار إلى الموضع الذي يدخل منه الحلقة من موضعين مختلفين، أحدهما على الذيل والآخر على الحلقة، لذا تحمل خانتان هذه القيمة. تعثر طريقة Floyd على مدخل الحلقة باستخدام مؤشرين، ولذلك تعثر على القيمة المكررة.
لماذا لا نستخدم مجموعة تجزئة أو نرتب المصفوفة؟
كلاهما يعثر على الإجابة في زمن O(n) أو O(n log n)، وفي برنامج حقيقي سيكون أيٌّ منهما مناسبًا. لكن المسألة تمنعهما عمدًا: فمجموعة التجزئة تستخدم ذاكرة إضافية O(n)، والفرز إما أن يغيّر nums أو يتطلب نسخة كاملة. وهذه القيود هي ما يدفعك إلى التفكير بمنظور الدورات.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def findDuplicate(nums):
# اكتب الكود هنااختبار #1
اختبار #2
وسيط
nums = [2, 5, 1, 3, 5, 4]
الإخراج المتوقع
5