فرز قائمة وفقًا للطلب المحدد بواسطة قائمة أخرى

Question

كيف يمكنني فرز عناصر القائمة أ بحيث يتبعون ترتيب قائمة أخرى (superset) ب؟ لا تفترض أي تكرارات.

على سبيل المثال أ قد تحتوي على [8 2 5 1] و ب قد تحتوي على [5 6 9 8 7 4 1 2 3] ، ولذا أود أن فرز أ لتصبح [5 8 1 2

أنا مهتم بطرق القيام بذلك بكفاءة ومع تعقيد وقت التشغيل الجيد.

Answer 1

إذا ب هو superset من أ, ، كنت فقط تفريغ أ في جدول التجزئة ، المسح الضوئي ب وإنشاء قائمة جديدة حيث أدخل كل عنصر من ب هذا وارد في جدول التجزئة. يستخدم O (A) ذاكرة إضافية و O (B) وقت التشغيل.

Answer 2

إليكم بعض الأفكار:

(في الوقت المعطى ، ن هو حجم أ و م هو حجم ب. التعقيدات الزمنية غير مبسطة.)

• لكل عنصر في ب, ، قم بالبحث الخطي عن أ لمعرفة ما إذا كان هذا العنصر موجود فيه. إذا كان الأمر كذلك ، فقم بتبديله بالعنصر الأول في أ هذا لم يتم وضعه بعد. تعقيد الوقت: O (NM)
• كما هو مذكور أعلاه ، ولكن وضع محتويات أولاً أ في بنية بحث فعالة لتجنب البحث الخطي. تعقيد الوقت: o (n + m) على افتراض O (1) البحث
• فرز ب. ثم ، لكل عنصر في أ, ، ابحث عن فهرسه (وهو مضمون للوجود) في الداخل ب باستخدام البحث الثنائي. سجل هذا الفهرس في صفيف إضافي بنفس حجم أ. استخدم هذه المجموعة من المؤشرات كمدخلات لمقارن يصرخ أ. تعقيد الوقت: O ((M log m) + (n log n) + (n log n))