Rotate Array

Q: מה קורה כש־k גדול מאורך המערך?

כל n צעדים מחזירים את המערך לסדר ההתחלתי שלו, לכן רק k mod n צעדים חשובים. סיבוב של [10, 20, 30] ב־7 צעדים זהה לסיבוב שלו בצעד אחד, שמניב את [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: המערך nums מסובב ימינה ב־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 צעדים זהה לסיבוב שלו בצעד אחד, שמניב את [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]