Rotate Array

Q: ماذا يحدث عندما تكون قيمة k أكبر من طول المصفوفة؟

كل n خطوات تعيد المصفوفة إلى ترتيبها الأصلي، لذا لا يهم سوى k mod n خطوة. تدوير [10, 20, 30] بمقدار 7 هو نفسه تدويرها بمقدار 1، مما يعطي [30, 10, 20] . عندما يكون k من مضاعفات n ، لا تتغير المصفوفة.

Q: كيف تُدوِّر مصفوفة إلى اليسار؟

الدوران إلى اليسار بمقدار k هو دوران إلى اليمين بمقدار n - (k mod n) . باستخدام عمليات العكس، اعكس أول k mod n قيمة، ثم بقية القيم، ثم المصفوفة بأكملها. كلاهما يستغرق زمنًا قدره O(n).

متوسطالمصفوفات والسلاسل النصية مؤشران

+10

لديك مصفوفة من الأعداد الصحيحة nums وعدد k. أدر المصفوفة إلى اليمين بمقدار k خطوات: في كل خطوة، تنتقل كل قيمة موضعًا واحدًا إلى اليمين، وتلتف القيمة الأخيرة لتصل إلى المقدمة. أعد المصفوفة بعد تدويرها.

قد تكون قيمة k أكبر بكثير من طول المصفوفة.

الدالة

rotate(nums: integer-array, k: integer) → integer-array

numsinteger-array: مصفوفة الأعداد الصحيحة المراد تدويرها
kinteger: كم خطوة للدوران إلى اليمين
تُرجعinteger-array: الأعداد التي دُوِّرت إلى اليمين بمقدار k خطوات

القيود

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
0 ≤ k ≤ 10⁹

أمثلة

المدخلات: nums = [4, 9, 1, 6, 3]k = 2
المخرجات: [6, 3, 4, 9, 1]
الشرح: خطوتان إلى اليمين تنقلان آخر قيمتين، 6 و3، إلى المقدمة. وتتحرك القيم الثلاث الأخرى بمقدارين إلى اليمين مع الحفاظ على ترتيبها: [6, 3, 4, 9, 1].

سؤال إضافي

هل يمكنك إجراء تدوير في المكان بنقل كل قيمة مباشرةً إلى (i + k) mod n، ومواصلة نقل القيمة التي تحل محلها؟ كم دورةً ينتج عن ذلك؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

كل n خطوات تعيد المصفوفة إلى موضع بدايتها، لذا اختزل k أولًا، الذي قد يصل إلى 10^9، إلى k mod n. ثم اكتب كل قيمة مباشرةً في فهرسها النهائي في مصفوفة ثانية، أو حقّق النتيجة نفسها داخل المصفوفة باستخدام ثلاث عمليات عكس وذاكرة إضافية مقدارها O(1).

انسخ كل قيمة إلى فهرسها الجديد

الفكرة

بعد k خطوات، تصبح القيمة عند الفهرس i في الموضع (i + k) mod n، لذا اكتبها هناك مباشرةً من دون تنفيذ الخطوات. اختزل k إلى k mod n أولًا: فالدوران بمقدار n يعيد كل قيمة إلى موضعها السابق، لذا عندما تكون k = 7 وn = 3، لا يتبقى سوى خطوة واحدة.

تمريرة واحدة تضع القيم n كلها: زمن O(n)، بالإضافة إلى ذاكرة O(n) للنتيجة. لا يمكنك الكتابة في nums نفسها بهذه الطريقة، لأن كل عملية كتابة ستستبدل قيمة لم تنقلها بعد.

الخوارزمية

اجعل n يساوي طول nums، واستبدل k بـ k mod n.
أنشئ مصفوفة نتائج طولها n.
لكل فهرس i، خزّن nums[i] في result[(i + k) mod n].
أعِد النتيجة.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = nums[i]
    return result

ثلاث عمليات عكس في مكانها

الفكرة

قسّم المصفوفة إلى A، وهي أول n-k قيمة، وB، وهي آخر k قيم. المصفوفة بعد تدويرها هي B متبوعةً بـA، مع بقاء ترتيب العناصر في كل كتلة كما كان. يؤدي عكس المصفوفة كلها إلى قلب ترتيب الكتل وترتيب العناصر داخل كل منها، لذا تأتي B أولًا لكن بترتيب معكوس، وينطبق الأمر نفسه على A. ويؤدي عكس كل كتلة مرة أخرى إلى استعادة ترتيب عناصرها.

بالنسبة إلى [4, 9, 1, 6, 3] وk = 2: يؤدي عكس كل شيء إلى [3, 6, 1, 9, 4]، وعكس أول عنصرين إلى [6, 3, 1, 9, 4]، وعكس العناصر الثلاثة الأخيرة إلى [6, 3, 4, 9, 1].

يُبدَّل كل عنصر مرتين كحد أقصى، لذا يكون الزمن O(n)، والذاكرة الإضافية بضعة متغيرات للفهرسة (وتكون O(n) في R، إذ تنسخ المتجه عندما تغيّره دالة المساعدة الخاصة بالعكس).

الخوارزمية

عيّن n لطول nums واستبدل k بـ k mod n.
اعكس المصفوفة بأكملها، من الفهرس 0 إلى n-1.
اعكس الكتلة الأولى، من الفهرس 0 إلى k-1.
اعكس الكتلة الثانية، من الفهرس k إلى n-1.
أعِد nums.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing

    def reverse(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    reverse(0, n - 1)  # the last k values come to the front, backwards
    reverse(0, k - 1)  # put the front block back in order
    reverse(k, n - 1)  # and the back block
    return nums

أخطاء شائعة وحالات حدّية

نسيان k mod n. عندما تكون k = 10^9، فإن التدوير خطوة بخطوة لا ينتهي أبدًا، كما أن عكس أول k قيمة يقرأ إلى ما بعد نهاية المصفوفة بكثير.
استخدام التقطيع دون أخذ باقي القسمة. في Python، تُرجع nums[-k:] + nums[:-k]، مع k = 7 وn = 3، المصفوفة دون تغيير، لأن كلا المقطعين يتوقف عند طرف المصفوفة.
العكس بترتيب خاطئ. عكس الكتلتين أولًا ثم المصفوفة بأكملها أخيرًا يؤدي إلى تدوير لليسار.
خطأ بمقدار واحد عند حد الكتلة: تنتهي الكتلة الأولى عند الفهرس k-1 وتبدأ الثانية عند k. في Lua وR، اللتين تبدآن العد من 1، تكون الكتلتان 1..k وk+1..n.

أسئلة شائعة3

ما هو التعقيد الزمني لتدوير المصفوفة؟

‏O(n) لكلٍّ من أسلوب النسخ والعمليات الثلاث للعكس، لأن كل قيمة تُنقل عددًا ثابتًا من المرات. اختزال k باستخدام k mod n أولًا يمنع قيمة k الضخمة من التأثير. أما التدوير خطوة واحدة في كل مرة فتكلّف O(n × k) بدلًا من ذلك.

ماذا يحدث عندما تكون قيمة k أكبر من طول المصفوفة؟

كل n خطوات تعيد المصفوفة إلى ترتيبها الأصلي، لذا لا يهم سوى k mod n خطوة. تدوير [10, 20, 30] بمقدار 7 هو نفسه تدويرها بمقدار 1، مما يعطي [30, 10, 20]. عندما يكون k من مضاعفات n، لا تتغير المصفوفة.

كيف تُدوِّر مصفوفة إلى اليسار؟

الدوران إلى اليسار بمقدار k هو دوران إلى اليمين بمقدار n - (k mod n). باستخدام عمليات العكس، اعكس أول k mod n قيمة، ثم بقية القيم، ثم المصفوفة بأكملها. كلاهما يستغرق زمنًا قدره O(n).

def rotate(nums, k):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

nums = [4, 9, 1, 6, 3]
k = 2

الإخراج المتوقع

[6, 3, 4, 9, 1]