Check if an Array Is Sorted
ניתן לך מערך של מספרים שלמים nums. החזר true אם הוא מסודר בסדר לא יורד, כלומר כל איבר קטן מהאיבר שאחריו או שווה לו, ו־false אחרת. איברים שכנים שווים זה בסדר: [2, 2, 3] נחשב למערך ממוין. מערך עם איבר אחד ממוין.
פונקציה
- numsinteger-array
- מערך המספרים השלמים שיש לבדוק
- מחזירהboolean
- true כאשר כל איבר קטן מהאיבר הבא או שווה לו, ו־false אחרת
אילוצים
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
דוגמאות
- קלט
- nums = [1, 3, 3, 7]
- פלט
- true
- הסבר
- כל שלב עולה או נשאר באותו גובה: מ־1 ל־3, מ־3 ל־3, מ־3 ל־7. מותר שהמספר 3 יופיע שוב, לכן התשובה היא
true.
- קלט
- nums = [2, 5, 4, 9]
- פלט
- false
- הסבר
- המעבר מ־5 ל־4 הוא ירידה. מעבר כזה אחד מספיק כדי שהמערך לא יהיה ממוין, אף על פי ש־9 בסוף הוא הערך הגדול ביותר, ולכן התשובה היא
false.
+16 בדיקות נסתרות בשליחה
שאלת המשך
איך תבדקו מערך שעשוי להיות ממוין בסדר עולה או בסדר יורד, ועדיין לעשות זאת במעבר אחד?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
אם מערך אינו ממוין, היכן בו אפשר לראות זאת? האם צריך להשוות בין איברים שנמצאים במרחק גדול זה מזה?
מספיק להשוות כל איבר לזה שמופיע מיד אחריו. איברים שכנים שווים מותרים; רק ירידה שוברת את הסדר.
עבור על זוגות סמוכים והחזר
falseבזוג הראשון שבו הערך השמאלי גדול מהערך הימני. אם אין זוג כזה, החזרtrue.
פתרון
מערך ממוין בדיוק כאשר אין בו איבר שגדול מהאיבר שמיד אחריו. אין צורך להשוות בין איברים המרוחקים זה מזה: אם כל זוג איברים סמוכים מסודר, גם המערך כולו מסודר. כך הבדיקה הופכת למעבר יחיד על פני n-1 זוגות, שאפשר לעצור בו בצעד הראשון שבו הסדר יורד.
מיין עותק והשווה
האינטואיציה
מערך ממוין הוא מערך שמיון שלו לא היה משנה אותו. לכן, צור עותק של nums, מיין את העותק ובדוק אם הוא תואם למערך המקורי, איבר אחר איבר. אם כל האיברים תואמים, nums כבר היה מסודר.
עבור [2, 5, 4, 9], העותק הממוין הוא [2, 4, 5, 9]. במיקום 1 מופיע 5 במערך המקורי ו־4 בעותק, לכן התשובה היא false. עבור [1, 3, 3, 7], העותק זהה והתשובה היא true.
הפתרון הזה נכון, אבל הוא עושה יותר ממה שהשאלה מבקשת. מיון דורש O(n log n), כלומר בערך 6 × 10^4 השוואות עבור 5000 מספרים, והעותק דורש O(n) זיכרון. הוא גם תמיד קורא את כל המערך, אפילו כשהזוג הראשון כבר אינו מסודר.
אלגוריתם
- העתיקו את
numsכדי שהמקור יישאר ללא שינוי. - מיינו את העותק בסדר מספרי עולה.
- השוו בין העותק ל-
numsמיקום אחר מיקום. - החזירו
trueאם כל המיקומים תואמים, אחרתfalse.
def isSorted(nums):
# sorted returns a new list, so nums itself is left as it was.
return sorted(nums) == numsהשווה כל זוג של שכנים
האינטואיציה
אין צורך בגרסה הממוינת כדי לדעת אם המערך ממוין. מערך מסודר בסדר לא יורד בדיוק כאשר כל איבר קטן או שווה לאיבר שמופיע מיד אחריו. מכיוון שאי־שוויוני ≤ הם טרנזיטיביים (a ≤ b וגם b ≤ c גוררים a ≤ c), בדיקת n-1 הזוגות הסמוכים מכסה כל זוג מיקומים.
עוברים עם i מ־1 עד n-1 ומשווים בין nums[i-1] ל־nums[i]. עבור [2, 5, 4, 9], הזוג (2, 5) תקין, והזוג (5, 4) יורד, ולכן מחזירים false מיד, בלי לבדוק את 9. איברים סמוכים שווים עוברים, כי רק > נכשל.
כל זוג מושווה פעם אחת, ולכן זמן הריצה הוא O(n), ואינדקס הלולאה הוא הזיכרון הנוסף היחיד, O(1). יש להשוות את שני הערכים ישירות במקום לחסר אותם: כאשר הערכים מגיעים עד 10^9, הפרש עלול לגלוש מטווח של int בן 32 סיביות.
אלגוריתם
- הרץ לולאה על
iמ-1 עדn-1. - אם
nums[i-1] > nums[i], החזרfalse. - אם הלולאה מסתיימת, החזר
true. איבר יחיד מדלג על הלולאה ונחשב ממוין.
def isSorted(nums):
for i in range(1, len(nums)):
# One step down anywhere breaks the order.
if nums[i - 1] > nums[i]:
return False
return True
מלכודות ומקרי קצה
הלולאה קצרה, לכן הבאגים נמצאים בקצוות שלה ובהשוואה.
- התייחסות לשכנים שווים כאל כישלון. בדיקת
nums[i-1] >= nums[i]דוחה את[1, 3, 3, 7]. רק ירידה ממשית (>) שוברת את הסדר. - קריאה מעבר לסוף. לולאה מ־
0עדn-1שמשווה ביןnums[i]ל־nums[i+1]חייבת לעצור צעד אחד מוקדם יותר, אחרת היא קוראת מחוץ למערך. התחלה ב־i = 1והשוואה ל־i-1מונעות את הבעיה. - חיסור במקום השוואה.
nums[i] - nums[i-1] >= 0נראה אותו דבר, אבל10^9 - (-10^9) = 2 × 10^9לא נכנס למספר שלם בן 32 סיביות, והוא גולש לערך שלילי. לכן מדווחים בטעות ש־[-1000000000, 1000000000]אינו ממוין. אותה גלישה שוברת גם משווה של qsort שנכתב בתורx - y. - מיון מספרים בתור טקסט. ב־JavaScript, הפעלת
sort()ללא פונקציית השוואה מציבה את10לפני9, ולכן בדיקה שמשלבת מיון והשוואה מחזירה תשובות שגויות.
שאלות נפוצות4
איך בודקים אם מערך ממוין?
השווה כל איבר לאיבר הבא. אם איבר כלשהו גדול מהאיבר שמימינו, המערך אינו ממוין ואפשר לעצור; אם מגיעים לסוף בלי למצוא איבר כזה, המערך ממוין. הפעולה אורכת O(n) ודורשת O(1) מקום נוסף.
למה מספיק לבדוק את השכנים?
יחס הסדר הוא טרנזיטיבי: אם a ≤ b וגם b ≤ c, אז a ≤ c. לכן, כשכל זוג סמוך נמצא בסדר, גם כל זוג מיקומים נמצא בסדר. ולהפך, בכל מערך שאינו ממוין יש לפחות זוג סמוך אחד שבו הערך יורד.
האם מערך שאיבריו שווים מסודר?
בסדר לא יורד, כן: [4, 4, 4] ממוין, כי אין איבר שגדול מהאיבר הבא. אם הבעיה מבקשת סדר עולה ממש, יש לשנות את הבדיקה כך שתדחה גם איברים שכנים שווים.
האם אפשר למיין עותק ולהשוות אותו למקור?
כן, והיא מחזירה את התשובה הנכונה, אבל היא דורשת זמן O(n log n) וזיכרון נוסף של O(n) עבור העותק. בדיקת השכנים מהירה יותר, אינה דורשת עותק, ויכולה להחזיר תשובה כבר בירידה הראשונה, בלי לקרוא את שאר הנתונים.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def isSorted(nums):
# כתבו כאן קודמקרה 1
מקרה 2
קלט
nums = [1, 3, 3, 7]
צפוי
true