التقليب من ناقلات

Question

لنفترض لدي ناقلات:

 0  1  2  3  4  5
[45,89,22,31,23,76]

و التقليب من المؤشرات:

[5,3,2,1,0,4]

هل هناك طريقة فعالة إلى اللجوء وفقا التقليب وبالتالي الحصول على:

[76,31,22,89,45,23]

تستخدم في معظم O(1) مساحة إضافية ؟

Answer 1

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

على سبيل المثال:

[5 3 2 1 0 4] الحالة الأولية

[4 3 2 1 0 5] تبادلت (5,4), 5 هو الآن في الموضع الصحيح ، ولكن 4 لا تزال خاطئة

[0 3 2 1 4 5] تبادلت (4,0), الآن كل 4 ، 0 في المواضع الصحيحة ، انتقل إلى الموقع التالي

[0 1 2 3 4 5] تبادلت (3,1), الآن 1 و 3 على حد سواء في المواضع الصحيحة ، انتقل إلى الموقع التالي

[0 1 2 3 4 5] جميع العناصر في المواضع الصحيحة ، نهاية.

ملاحظة:

لأن كل عملية مقايضة يضع واحدة على الأقل (من اثنين) عناصر في الموضع الصحيح ، نحن بحاجة أكثر من أي ن مثل هذه المقايضات تماما.

Answer 2

وحل زاك هو جيد جدا.

ومع ذلك، كنت أتساءل لماذا لا يوجد أي حاجة لفرز. إذا كان لديك التقليب من المؤشرات، استخدم القيم كمؤشر للمجموعة القديمة.

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

وعلى سبيل المثال:

a = [45,89,22,31,23,76];
b = [5,3,2,1,0,4]

والآن إذا كنت تريد أن لوب من خلال القيم في على على ، أو يمكنك أن تفعل شيئا مثل (الزائفة رمز):

for i=0 to 4
{
    process(a[i]);
}

إذا كنت تريد أن يتكرر خلال القيم في النظام الجديد، القيام به:

for i=0 to 4
{
    process(a[b[i]]);
}

وكما ذكر سابقا، قد يكون هذا soluion كافية في كثير من الحالات، ولكن لا يجوز في بعض الحالات الأخرى. وبالنسبة للحالات الأخرى يمكنك استخدام الحل عن طريق Zach.But في الحالات حيث هذا الحل يمكن استخدامها، فمن الأفضل للا حاجة لفرز على الإطلاق.