Squares of a Sorted Array
ניתן לך מערך של מספרים שלמים nums שממוינים בסדר לא יורד. הוא עשוי להכיל ערכים שליליים. העלה בריבוע כל ערך והחזר את הריבועים כמערך חדש, שגם הוא ממוין בסדר לא יורד.
פונקציה
- numsinteger-array
- המערך הממויין של מספרים שלמים, כולל מספרים שליליים
- מחזירהinteger-array
- הריבוע של כל ערך, ממוינים בסדר לא יורד
אילוצים
1 ≤ nums.length ≤ 4000-104 ≤ nums[i] ≤ 104numsממוינת בסדר שאינו יורד.
דוגמאות
- קלט
- nums = [-6, -2, 1, 3, 7]
- פלט
- [1, 4, 9, 36, 49]
- הסבר
- הריבועים בסדר המקורי הם 36, 4, 1, 9 ו-49. הערכים השליליים -6 ו-2 נותנים ריבועים גדולים, ולכן המיון מעביר את 36 קרוב לסוף:
[1, 4, 9, 36, 49].
- קלט
- nums = [-9, -4, -1]
- פלט
- [1, 16, 81]
- הסבר
- כל הערכים שליליים, ולכן הריבועים מתקבלים בסדר הפוך: 81, 16, 1 הופכים ל־
[1, 16, 81].
+14 בדיקות נסתרות בשליחה
שאלת המשך
העלאה בריבוע ומיון אורכים O(n log n). האם תוכלו לעשות זאת ב־O(n)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
העלו בריבוע את
[-6, -2, 1, 3, 7]ביד. איזה חלק במערך מאבד את הסדר שלו, ולמה?הריבוע הגדול ביותר מתקבל תמיד מהערך הראשון או מהערך האחרון של
nums, כי שני הערכים האלה הם הרחוקים ביותר מ־0.הצביעו עם מצביע אחד על כל אחד מהקצוות. השוו בין שני הריבועים, כתבו את הגדול יותר בסוף התוצאה, והזיזו את המצביע הזה פנימה. חזרו על הפעולה עד שכל המיקומים יתמלאו.
פתרון
העלאה בריבוע שומרת על הסדר של הערכים הלא-שליליים, אך הופכת את הסדר של הערכים השליליים, ולכן הריבועים אינם ממוינים. מיון שלהם מחדש עובד, אבל מתעלם מהסדר שבו קיבלת אותם. העובדה החשובה: הריבוע הגדול ביותר מגיע תמיד מאחד משני הקצוות של nums. השווה בין שני הקצוות, הצב את הריבוע הגדול יותר בסוף התוצאה, והתקדם פנימה.
ריבוע, ואז מיון
האינטואיציה
בנה מערך חדש שבו כל ערך מועלה בריבוע, ואז מיין אותו. ריבועים לעולם אינם שליליים, והמיון מסדר אותם בלי קשר למקור שלהם.
עבור [-6, -2, 1, 3, 7] הריבועים הם [36, 4, 1, 9, 49], והמיון נותן [1, 4, 9, 36, 49].
עלות המיון היא O(n log n). זה מהיר מספיק כאן, אבל הוא מתייחס לקלט כאילו אין לו סדר כלל. הגישה הבאה מנצלת את הסדר ודורשת מעבר אחד.
אלגוריתם
- צרו מערך עם
x * xעבור כלxב-nums. - מיינו אותו בסדר מספרי עולה.
- החזירו אותו.
def sortedSquares(nums):
return sorted(x * x for x in nums)שני מצביעים משני הקצוות
האינטואיציה
חשבו על הריבועים כעל המרחק מ־0, בריבוע. במערך ממוין, הערכים הרחוקים ביותר מ־0 נמצאים בשני הקצוות: הערך השלילי ביותר משמאל והערך החיובי ביותר מימין. לכן הריבוע הגדול ביותר הוא nums[left]² או nums[right]², ולעולם לא של ערך שנמצא ביניהם.
השאירו את left ב־0 ואת right ב־n-1, ומלאו את התוצאה מהמיקום האחרון שלה לאחור. בכל צעד, השוו בין הריבועים שבשני הקצוות, כתבו את הגדול יותר במיקום הנוכחי והזיזו את המצביע הזה פנימה. מה שנשאר בין המצביעים הוא שוב מערך ממוין, ולכן אותו עיקרון תקף בכל צעד.
עבור [-6, -2, 1, 3, 7]: 49 גדול מ־36 ונכנס למקום האחרון. אחר כך 36 גדול מ־9, 9 גדול מ־4, 4 גדול מ־1, וה־1 ממלא את מיקום 0. התוצאה היא [1, 4, 9, 36, 49]. כל ערך ממוקם פעם אחת: זמן ריצה O(n), ומערך התוצאה הוא המערך הנוסף היחיד.
אלגוריתם
- צרו מערך תוצאות באורך
n. הגדירו אתleftכ־0 ואתrightכ־n-1. - עברו על המיקומים של
pos, מ־n-1ועד 0. - השוו בין
nums[left]²לביןnums[right]². - כתבו את הריבוע הגדול יותר במיקום
posוהזיזו את המצביע הזה צעד אחד פנימה. - החזירו את התוצאה.
def sortedSquares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
# the largest square left is always at one of the two ends
for pos in range(n - 1, -1, -1):
left_sq = nums[left] * nums[left]
right_sq = nums[right] * nums[right]
if left_sq > right_sq:
result[pos] = left_sq
left += 1
else:
result[pos] = right_sq
right -= 1
return result
מלכודות ומקרי קצה
הגרסה עם שני המצביעים קצרה, אבל כמה פרטים עלולים לשבש אותה.
- מילוי התוצאה מההתחלה. הריבוע הקטן ביותר נמצא במקום שבו הערכים חוצים את 0, וזה יכול להיות בכל מקום באמצע. הקצוות מצביעים רק על הריבוע הגדול ביותר. מלאו מהסוף.
- השוואה בין
nums[left]ל-nums[right]במקום בין הריבועים שלהם או הערכים המוחלטים שלהם. -6 קטן מ-3, אבל הריבוע שלו גדול יותר. - עצירה כש-
leftפוגש אתright. כשהם שווים, עדיין נשאר ערך אחד שלא שובץ; עברו בלולאה על כל מיקום בתוצאה, או השתמשו ב-left <= right. - קלט שכולו שלילי או כולו חיובי. עם
[-9, -4, -1]המצביע השמאלי עושה את כל העבודה, ועם[2, 5, 8]המצביע הימני עושה זאת. בשני המקרים עדיין צריך להחזיר פלט ממוין. - ב-JavaScript וב-TypeScript, קריאה ל-
sort()ללא פונקציית השוואה ממיינת מספרים כטקסט, ולכן[1, 4, 36, 9]הופך ל-[1, 36, 4, 9]. העבירו את(a, b) => a - b.
שאלות נפוצות4
מהי סיבוכיות הזמן של ריבועים של מערך ממוין?
פתרון שני המצביעים פועל בזמן O(n): כל ערך מועלה בריבוע וממוקם פעם אחת. העלאה בריבוע ואז מיון עולים O(n log n). בשתי השיטות נדרש זיכרון של O(n) עבור התוצאה.
למה הריבוע הגדול ביותר נוצר מאחד משני הקצוות?
ריבוע גדל ככל שהמרחק מ־0 גדל. במערך ממוין, הערך הרחוק ביותר מתחת ל־0 הוא הראשון, והערך הרחוק ביותר מעל ל־0 הוא האחרון. כל ערך שביניהם קרוב יותר ל־0 מאחד מהם, ולכן הריבוע שלו לא יכול להיות הגדול ביותר.
אפשר למלא את התוצאה מההתחלה במקום זאת?
כן, אבל קודם עליך למצוא היכן הערכים חוצים את 0, למשל באמצעות חיפוש בינארי. לאחר מכן שני מצביעים מתקדמים החוצה מנקודה זו, כמו במיזוג של שתי רשימות ממוינות: השליליים נקראים מימין לשמאל והלא־שליליים משמאל לימין. מילוי מהסוף מייתר את החיפוש, כי הקצוות ידועים מראש.
האם Squares of a Sorted Array היא בעיית מיזוג?
כן, בתחפושת. הריבועים של הערכים השליליים יוצרים רשימה ממוינת אחת (שנקראת מימין לשמאל), והריבועים של הערכים שאינם שליליים יוצרים רשימה אחרת. שילוב שלהן הוא שלב המיזוג של מיון מיזוג, ולכן אפשר לבצע אותו במעבר ליניארי אחד.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def sortedSquares(nums):
# כתבו כאן את הקודמקרה 1
מקרה 2
קלט
nums = [-6, -2, 1, 3, 7]
צפוי
[1, 4, 9, 36, 49]