Move Zeroes

Q: איך מעבירים אפסים לסוף בלי לשנות את הסדר של שאר האיברים?

החזק אינדקס write עבור המקום הפנוי הבא בתחילת המערך, וסרוק באמצעות אינדקס שני. כל ערך שאינו אפס שתמצא מועבר למקום של write באמצעות החלפה, ו- write מתקדם צעד אחד ימינה. הערכים ממוקמים לפי הסדר שבו מצאת אותם, כך שהסדר היחסי שלהם לעולם אינו משתנה.

Q: האם אפשר להזיז אפסים עם פחות כתיבות?

כן. במקום להחליף, מעתיקים כל ערך שאינו אפס אל nums[write] , ולאחר הסריקה ממלאים כל מקום מ־ write ועד הסוף ב־0. כך כותבים לכל מיקום לכל היותר פעם אחת. אפשר גם לדלג על החלפה כאשר read שווה ל־ write , מכיוון שהערך יוחזר למקום שבו הוא כבר נמצא.

קלשני מצביעים

+10

נתון לך מערך של מספרים שלמים nums. העבר כל 0 לסוף המערך ושמור על הסדר המקורי של שאר הערכים. החזר את המערך לאחר הסידור מחדש, שאורכו זהה לאורך של nums.

פונקציה

moveZeroes(nums: integer-array) → integer-array

numsinteger-array: מערך המספרים השלמים שיש לסדר מחדש
מחזירהinteger-array: nums עם הערכים שאינם אפס תחילה, בסדר המקורי שלהם, וכל 0 בסוף

אילוצים

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

דוגמאות

קלט: nums = [0, 4, 0, 7, 2]
פלט: [4, 7, 2, 0, 0]
הסבר: הערכים שאינם 0 הם 4, 7 ו-2, והם נשארים בסדר הזה בתחילת הרשימה. שני ערכי ה-0 ממלאים את שני המקומות האחרונים.

+14 בדיקות נסתרות בשליחה

שאלת המשך

האם תוכל להעביר כל 0 להתחלה במקום זאת, תוך שמירה על סדר הערכים האחרים, במעבר אחד ועם זיכרון נוסף של O(1)?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

העברת האפסים לסוף אינה החלק הקשה. שמירה על הסדר המקורי של הערכים האחרים היא החלק הקשה, ולכן אי אפשר להחליף כל 0 באיבר האחרון. חלקו את המערך לאזור קדמי שמכיל את הערכים שאינם אפס שנמצאו עד כה, ולשאר האיברים. אינדקס אחד קורא כל איבר, אינדקס שני מסמן היכן שייך הערך הבא שאינו אפס, ומעבר יחיד משלים את העבודה במקום.

העתיקו את הערכים שאינם אפס

האינטואיציה

בנו מערך חדש. עברו על nums והעתיקו כל ערך שאינו 0, לפי הסדר שבו פוגשים אותו. לאחר מכן הוסיפו אפסים עד שהמערך החדש יהיה באורך של nums. מספר האפסים שתוסיפו הוא מספר הערכים שדילגתם עליהם.

עבור [0, 4, 0, 7, 2], שלב ההעתקה נותן [4, 7, 2], ושני אפסים הופכים אותו ל-[4, 7, 2, 0, 0]. הסדר נכון כי אתם מעתיקים את הערכים לפי הסדר שבו אתם קוראים אותם.

כל איבר נקרא פעם אחת ונכתב פעם אחת, ולכן זמן הריצה הוא O(n). המערך השני דורש זיכרון O(n), שאותו הגישה הבאה חוסכת.

אלגוריתם

צרו מערך תוצאות ריק.
עבור כל ערך ב־nums, הוסיפו אותו לתוצאה אם הוא אינו 0.
הוסיפו אפסים עד שיהיו בתוצאה מספר איברים זהה לזה שב־nums.
החזירו את התוצאה.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

שני מצביעים, החלפה במקום

האינטואיציה

השתמשו בשני אינדקסים. read עובר על כל איבר משמאל לימין. write מציין היכן צריך להיות הערך הבא שאינו אפס. אחרי כל צעד מתקיימים שני דברים: כל מה שלפני write הוא הערכים שאינם אפס שנצפו עד כה, בסדר המקורי שלהם, וכל מה שבין write ל-read הוא 0.

כאשר nums[read] אינו 0, החליפו אותו עם nums[write] והזיזו את write צעד אחד ימינה. הערך שמגיע ל-read הוא 0 מאזור האפסים, או אותו ערך כאשר שני האינדקסים שווים. ערכים שאינם אפס מדלגים רק מעל אפסים, ולא מעל ערכים אחרים, ולכן הסדר שלהם נשמר.

עבור [0, 4, 0, 7, 2]: הערך 4 באינדקס 1 מתחלף עם הערך שבאינדקס 0, והתוצאה היא [4, 0, 0, 7, 2]. הערך 7 באינדקס 3 מתחלף עם הערך שבאינדקס 1, והתוצאה היא [4, 7, 0, 0, 2]. הערך 2 באינדקס 4 מתחלף עם הערך שבאינדקס 2, והתוצאה היא [4, 7, 2, 0, 0]. מעבר אחד וללא מערך שני: זמן O(n) וזיכרון O(1).

אלגוריתם

הגדר את write ל־0.
העבר את read מהאינדקס הראשון לאחרון.
אם nums[read] אינו 0, החלף בין nums[read] ל־nums[write], ואז הוסף 1 ל־write.
החזר את nums.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

מלכודות ומקרי קצה

השגיאות הנפוצות בדרך כלל משבשות את הסדר של הערכים האחרים או מדלגות על איברים.

החלפה של כל 0 עם האיבר האחרון מזיזה את האפסים, אבל מערבבת את השאר: [0, 4, 7] הופך ל־[7, 4, 0].
מחיקת אפסים מהמערך בזמן שאינדקס עובר עליו גורמת לדילוג על איברים. ב־[0, 0, 5], מחיקת אינדקס 0 מזיזה את ה־0 השני לאינדקס 0, בזמן שהלולאה ממשיכה לאינדקס 1. כל מחיקה גם מזיזה את שאר המערך, ולכן הלולאה היא בסיבוכיות O(n²).
בדקו x != 0, ולא x > 0. ערכים שליליים אינם אפסים: [-1, 0, -2] חייב להפוך ל־[-1, -2, 0], אבל עם x > 0 גרסת ההעתקה מחזירה [0, 0, 0].
מערך ללא אפסים, או שמכיל אפסים בלבד, חייב לחזור ללא שינוי. בגרסת ההחלפה, read ו־write נשארים שווים עד לאפס הראשון, ולכן ההחלפות האלה לא משנות דבר.
ב־Lua וב־R, המערכים מתחילים ב־1, ולכן גם write מתחיל ב־1.

שאלות נפוצות4

מהי סיבוכיות הזמן של Move Zeroes?

O(n). שתי הגישות קוראות כל איבר פעם אחת. העתקת הערכים שאינם אפס למערך חדש דורשת זיכרון נוסף של O(n), ואילו ההחלפה באמצעות שני מצביעים מתבצעת בתוך המערך ודורשת זיכרון נוסף של O(1).

איך מעבירים אפסים לסוף בלי לשנות את הסדר של שאר האיברים?

החזק אינדקס write עבור המקום הפנוי הבא בתחילת המערך, וסרוק באמצעות אינדקס שני. כל ערך שאינו אפס שתמצא מועבר למקום של write באמצעות החלפה, ו-write מתקדם צעד אחד ימינה. הערכים ממוקמים לפי הסדר שבו מצאת אותם, כך שהסדר היחסי שלהם לעולם אינו משתנה.

האם אפשר להזיז אפסים עם פחות כתיבות?

כן. במקום להחליף, מעתיקים כל ערך שאינו אפס אל nums[write], ולאחר הסריקה ממלאים כל מקום מ־write ועד הסוף ב־0. כך כותבים לכל מיקום לכל היותר פעם אחת. אפשר גם לדלג על החלפה כאשר read שווה ל־write, מכיוון שהערך יוחזר למקום שבו הוא כבר נמצא.

למה Move Zeroes היא בעיית שני מצביעים?

מצביע אחד קורא כל איבר, והאחר מסמן את סוף החלק הקדמי שהושלם. שניהם נעים רק קדימה, ולכן יחד הם מבצעים מעבר יחיד. אותה תבנית של קריאה וכתיבה מסירה כפילויות ממערך ממוין או מסננת ערך כלשהו מתוך מערך במקום.

Python

def moveZeroes(nums):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

nums = [0, 4, 0, 7, 2]

צפוי

[4, 7, 2, 0, 0]