Remove Duplicates from Sorted Array
لديك مصفوفة من الأعداد الصحيحة nums مرتبة ترتيبًا غير تنازلي، لذا تكون القيم المتساوية متجاورة. أعد القيم المميزة في nums، كلًّا منها مرة واحدة، وبالترتيب الذي تظهر به. على سبيل المثال، تعطي [2, 2, 5] القيمة [2, 5].
الدالة
- numsinteger-array
- الأعداد الصحيحة، مرتبة ترتيبًا غير تنازلي
- تُرجعinteger-array
- القيم المميّزة لـ nums، بترتيب تصاعدي
القيود
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104numsمرتبة ترتيبًا غير تنازلي.
أمثلة
- المدخلات
- nums = [1, 1, 2, 3, 3, 3]
- المخرجات
- [1, 2, 3]
- الشرح
- يظهر
1مرتين و3ثلاث مرات. يؤدي الإبقاء على نسخة واحدة من كل منها إلى[1, 2, 3].
- المدخلات
- nums = [-2, 0, 0, 5]
- المخرجات
- [-2, 0, 5]
- الشرح
- يتكرر
0فقط. تعمل القيم السالبة بالطريقة نفسها، لذا تكون الإجابة[-2, 0, 5].
- المدخلات
- nums = [7, 7, 7]
- المخرجات
- [7]
- الشرح
- كل القيم هي
7، لذا لا يتبقى سوى7واحد.
+15 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك فعل ذلك باستخدام ذاكرة إضافية O(1)، عن طريق إعادة كتابة nums في مكانها بدلًا من إنشاء مصفوفة ثانية؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
بما أن
numsمرتبة، فإن جميع نسخ القيمة الواحدة تشكّل مجموعة متتالية. كيف يمكنك معرفة أن قيمةً ما هي الأولى في مجموعتها المتتالية من دون تذكّر كل القيم التي رأيتها؟تبدأ القيمة سلسلة جديدة بالضبط عندما تختلف عن آخر قيمة احتفظت بها. لذا لا تقارن إلا بقيمة واحدة، ويمكنك الكتابة فوق المصفوفة من بدايتها أثناء المتابعة.
احتفظ بمؤشر للكتابة
k، وابدأ من 1 لأنnums[0]يُحتفظ به دائمًا. اقرأ كل قيمة لاحقة؛ وعندما تختلف عنnums[k-1]، انسخها إلىnums[k]وأضف 1 إلىk. أعد أولkقيم.
الحل
تعني إزالة العناصر المكررة من مصفوفة عشوائية تذكّر كل قيمة رأيتها. أما الإدخال المرتب فيلغي هذه الحاجة: فنسخ القيمة تكون متجاورة، لذا تكون القيمة جديدة بالضبط عندما تختلف عن آخر قيمة احتفظت بها. يحوّل ذلك المهمة إلى مرور واحد باستخدام فهرسين ومن دون ذاكرة إضافية.
تذكّر القيم التي تمت رؤيتها في مجموعة تجزئة
الفكرة
مرّ على nums واحتفظ بمجموعة من القيم التي أضفتها بالفعل إلى الإجابة. عندما لا تكون القيمة موجودة في المجموعة، ألحِقها بالإجابة وأضفها إلى المجموعة؛ وعندما تكون موجودة، فتجاوزها. بالنسبة إلى [1, 1, 2, 3, 3, 3]، تكبر الإجابة لتصبح [1]، ثم [1, 2]، ثم [1, 2, 3]، ويُتجاوز كل تكرار لاحق.
تُلحَق كل قيمة عند ظهورها للمرة الأولى، ولا تُلحَق مرة أخرى أبدًا، وبالترتيب الذي تصادفها فيه، لذا تكون الإجابة صحيحة. لا تستفيد هذه الطريقة مطلقًا من حقيقة أن nums مرتبة؛ إذ ستعمل مع أي مصفوفة.
يستغرق البحث في المجموعة O(1) في المتوسط، لذا يستغرق المرور O(n) من الوقت، لكن يمكن لكل من المجموعة والإجابة أن تحتوي على n قيمة: مساحة إضافية مقدارها O(n). في C، حيث لا توجد مجموعة مضمّنة، تؤدي مصفوفة من العلامات للقيم الممكنة وعددها 2 × 10^4 + 1 الغرض نفسه.
الخوارزمية
- أنشئ مجموعة فارغة
seenوقائمة فارغةresult. - لكل قيمة في
nums، تحقّق مما إذا كانت موجودة فيseen. - إذا لم تكن موجودة، فأضفها إلى
seenوألحِقها بـresult. - أعِد
result.
def removeDuplicates(nums):
seen = set()
result = []
for num in nums:
if num not in seen:
seen.add(num)
result.append(num)
return resultالضغط في المكان باستخدام مؤشر الكتابة
الفكرة
في الإدخال المرتب، تكوّن جميع نسخ القيمة سلسلةً واحدة، لذا تكون القيمة جديدةً بالضبط عندما تختلف عن آخر قيمة احتفظت بها. وهذا يتطلب مقارنة واحدة، لا مجموعة.
استخدم مؤشرين. يمرّ مؤشر القراءة i على كل قيمة. ويحدّد مؤشر الكتابة k نهاية الجزء المحتفَظ به: يحتوي nums[0] إلى nums[k-1] دائمًا على القيم المميّزة التي عُثر عليها حتى الآن. ابدأ بـ k = 1، لأن القيمة الأولى يُحتفَظ بها دائمًا. عندما تختلف nums[i] عن nums[k-1]، انسخها إلى nums[k] ثم حرّك k إلى الأمام.
في [1, 1, 2, 3, 3, 3]: تقرأ i = 1 القيمة 1 للمرة الثانية، فلا يحدث شيء. تقرأ i = 2 القيمة 2، وهي تختلف عن nums[0] = 1، لذا تُكتَب عند الفهرس 1 ويصبح k مساويًا لـ 2. تكتب i = 3 القيمة 3 عند الفهرس 2 ويصبح k مساويًا لـ 3. تتطابق آخر قيمتي 3 مع nums[2]، لذا يجري تخطيهما. أصبحت الخانات الثلاث الأولى الآن تقرأ [1, 2, 3].
لا تتجاوز الكتابة القراءة أبدًا، لأن k لا يزيد أبدًا على i، لذا لا تستبدل قيمةً قبل قراءتها. يتطلب المرور الواحد زمنًا قدره O(n)، وباستثناء القيم المُعادة، تستخدم عددين صحيحين: مساحة إضافية قدرها O(1).
الخوارزمية
- عيّن
k = 1: يتم الاحتفاظ دائمًا بـnums[0]. - كرّر
iمن 1 إلى الفهرس الأخير. - إذا كان
nums[i]مختلفًا عنnums[k-1]، فعيّنnums[k] = nums[i]وزِدkبمقدار 1. - أعِد أول
kقيم منnums.
def removeDuplicates(nums):
# nums[0:k] holds the distinct values found so far, in order.
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[k - 1]:
nums[k] = nums[i]
k += 1
return nums[:k]
أخطاء شائعة وحالات حدّية
مؤشر الكتابة قصير، وتتعلق أخطاؤه بالقيمة التي تقارن بها.
- مقارنة
nums[i]معnums[i+1]بينما تصل قيمةiإلى الفهرس الأخير. تقرأ المقارنة الأخيرة عنصرًا يتجاوز نهاية المصفوفة. - بدء
kبالقيمة 0. عندها تُقارَن القيمة الأولى معnums[-1]، وهو فهرس خارج النطاق أو، في Python، العنصر الأخير. - إرجاع المصفوفة كلها بدلًا من أول
kقيمة منها. تظل القيم القديمة في الذيل، لذا ستُعاد[1, 1, 2]على هيئة[1, 2, 2]. - إنشاء الإجابة بالتكرار على مجموعة تجزئة. لا تحتفظ مجموعة التجزئة في معظم اللغات بأي ترتيب، لذا قد تظهر القيم بترتيب عشوائي؛ ألحِق كل قيمة بقائمة عند مصادفتها لأول مرة بدلًا من ذلك.
- في Lua وR، تبدأ المصفوفات من 1. الجزء المحتفَظ به هو
nums[1]إلىnums[k]، وتكون المقارنة معnums[k]، لا معnums[k-1].
أسئلة شائعة4
ما هو التعقيد الزمني لخوارزمية إزالة التكرارات من مصفوفة مرتبة؟
يقرأ حلّ مؤشر الكتابة كل قيمة مرة واحدة، لذا يعمل في زمن O(n). وبالإضافة إلى القيم التي يعيدها، يستخدم مساحة إضافية قدرها O(1): فهرسان.
لماذا يجب ترتيب المصفوفة؟
يضع الترتيب كل نسخة من القيمة ضمن مجموعة متجاورة، لذا تكون القيمة جديدة فقط عندما تختلف عن آخر قيمة تم الاحتفاظ بها. في مصفوفة غير مرتبة، قد تظهر نسخة بعيدًا عن موضع النسخة الأولى، وستحتاج إلى مجموعة تجزئة لتذكّر كل قيمة تمت رؤيتها، وهذا يكلّف مساحة إضافية قدرها O(n).
كيف تزيل العناصر المكررة في مكانها دون استخدام ذاكرة إضافية؟
احتفظ بمؤشر كتابة k بجانب مؤشر القراءة. تحتوي الخانات k الأولى على القيم المميزة حتى الآن. عندما تختلف القيمة التي تقرؤها عن nums[k-1]، انسخها إلى nums[k] وزِد k. لا يتجاوز مؤشر الكتابة مؤشر القراءة أبدًا، لذا لا يُستبدل أي شيء قبل قراءته.
كيف تسمح بظهور كل قيمة مرتين كحد أقصى؟
قارِن بالقيمة التي تسبق بموقعين في الجزء المحتفَظ به بدلًا من موقع واحد: انسخ nums[i] عندما يكون k < 2 أو عندما تختلف عن nums[k-2]. إذا كانت تساوي nums[k-2]، فهذا يعني أن الجزء المحتفَظ به ينتهي بالفعل بنسختين منها. تتيح الفكرة نفسها الاحتفاظ بحد أقصى m نسخ باستخدام nums[k-m].
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def removeDuplicates(nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [1, 1, 2, 3, 3, 3]
المتوقع
[1, 2, 3]