إزالة التكرارات في مكانها

لديك مصفوفة مرتبة، وعليك الاحتفاظ بنسخة واحدة من كل قيمة من دون استخدام مصفوفة إضافية. يوفر التنفيذ في المكان الذاكرة، وهو سؤال شائع في المقابلات. 🧹

عندما تكون المصفوفة مرتبة، تكون كل قيمة مكررة ملاصقة لنظيرتها. لذلك لا تحتاج إلا إلى مقارنة العناصر المتجاورة، وليس المصفوفة بأكملها.

استخدم مؤشر slow لتحديد آخر قيمة احتفظت بها، ومؤشرًا سريعًا يتقدم في المصفوفة بحثًا عن قيمة جديدة.

فكّر في slow على أنه موضع الكتابة: كل ما يقع عنده أو قبله نُظّف بالفعل وأصبح فريدًا.

يكتفي المؤشر fast بالقراءة إلى الأمام. فهو يسبق غيره، ولا ينبه slow إلا عندما يعثر على قيمة لم يُحتفظ بها بعد.

إذا كانت a[fast] تساوي a[slow]، فهي تكرار، ولذلك لا تفعل شيئًا سوى زيادة fast. وهكذا يتم تجاوز القيمة المكررة بهدوء.

عندما تختلف a[fast]، حرّك slow إلى الأمام وانسخ القيمة الجديدة في موضعه. يؤدي ذلك إلى استبدال التكرارات القديمة ببيانات فريدة جديدة.

بعد انتهاء الفحص، تكون قيمة slow + 1 هي عدد القيم الفريدة، وجميعها مجمعة في بداية المصفوفة.

كل ما يوجد بعد البادئة الفريدة هو بيانات متبقية غير مهمة. فالمسألة تهتم بالعناصر slow + 1 الأولى فقط، لذا اترك الذيل كما هو.

تحتوي المصفوفة الفارغة على صفر من القيم الفريدة. تحقّق من n == 0 قبل البدء حتى لا تقرأ بعد نهاية المصفوفة.

يعمل هذا النمط البطيء-السريع في زمن O(n) وبمساحة إضافية O(1)، وهو بالضبط ما تتطلبه قيود الذاكرة الصارمة.

أنت تزيل التكرارات في المكان من مصفوفة مرتبة باستخدام مؤشري slow وfast.

في المصفوفة المرتبة، يزيل زوج slow-fast التكرارات في مرور واحد بتعقيد O(n) ومن دون مساحة إضافية، ويعيد slow + 1 بوصفه عدد القيم الفريدة. 🎉