Count Inversions
בהינתן רשימה של מספרים שלמים nums, החזר את מספר ההיפוכים: זוגות של אינדקסים i < j שעבורם nums[i] > nums[j], כלומר ערך גדול יותר מופיע לפני ערך קטן יותר. ערכים שווים לעולם אינם יוצרים היפוך, וברשימה ממוינת אין היפוכים.
פונקציה
- numsinteger-array
- רשימת המספרים השלמים
- מחזירהinteger
- מספר הזוגות i < j שעבורם nums[i] > nums[j]
אילוצים
1 ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- התשובה היא לכל היותר
n(n-1)/2 < 2 × 108, ולכן היא נכנסת למספר שלם מסומן בן 32 סיביות.
דוגמאות
- קלט
- nums = [5, 3, 8, 1, 4]
- פלט
- 6
- הסבר
- 5 מופיע לפני 3, 1 ו-4: 3 זוגות. 3 מופיע לפני 1, ו-8 לפני 1 ו-4: עוד 3. 1 ו-4 מסודרים לפי הסדר, לכן הסך הכול הוא 6.
- קלט
- nums = [2, 2, 2, 1]
- פלט
- 3
- הסבר
- כל אחד משלושת המספרים 2 מופיע לפני המספר 1, ולכן יש 3 היפוכים. שני מספרים שווים 2 אינם נספרים לעולם, כי היפוך דורש שהערך הראשון יהיה גדול ממש.
- קלט
- nums = [-1, 0, 7, 7]
- פלט
- 0
- הסבר
- הרשימה ממוינת, ושני המספרים 7 השווים אינם נחשבים, ולכן התשובה היא 0.
שאלת המשך
מה משתנה אם זוג נחשב רק כאשר nums[i] > 2 × nums[j]? האם מיון מיזוג עדיין יכול לספור את הזוגות האלה ב־O(n log n)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
חלקו את הרשימה לחצי שמאלי ולחצי ימני. כל היפוך נמצא בתוך החצי השמאלי, בתוך החצי הימני או בזוג שבו ערך אחד נמצא בכל צד. האם תוכלו לספור את שלוש הקבוצות בנפרד?
מיון של כל חצי אינו משנה את מספר הזוגות שחוצים את האמצע, מכיוון שכל ערך בחצי השמאלי נשאר משמאל לכל ערך בחצי הימני. וכששני החצאים ממוינים, אפשר לספור את הזוגות שחוצים את האמצע בקבוצות במקום אחד־אחד.
השתמש במיון מיזוג. בזמן מיזוג שני חצאים ממוינים, בכל פעם שלוקחים ערך מהחצי הימני, הוא קטן מכל הערכים שעדיין ממתינים בחצי השמאלי, ולכן יש להוסיף את מספר הערכים שנותרו שם. במקרה של שוויון, לוקחים מהחצי השמאלי, כך שערכים שווים לעולם לא נספרים.
פתרון
בדיקת כל זוג דורשת בערך n² / 2 השוואות. מיון מיזוג סופר זוגות בקבוצות: כאשר ערך מהחצי הימני ממוקם במהלך מיזוג, כל ערך מהחצי השמאלי שעדיין ממתין גדול ממנו והופיע לפניו. חיסור אחד סופר את כל הקבוצה הזאת, ולכן הספירה אינה מוסיפה דבר מעבר למיון ב־O(n log n).
בדקו כל זוג
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
עבור כל אינדקס i, בדוק כל אינדקס מאוחר יותר j והוסף 1 כאשר nums[i] > nums[j]. זו ההגדרה, וההשוואה המחמירה לא כוללת ערכים שווים.
העלות היא n(n-1)/2 השוואות: כמעט 2 × 10^8 עבור 2 × 10^4 ערכים, והכפלת n מגדילה אותה פי ארבעה.
אלגוריתם
- הגדר
count = 0. - עבור כל
iמ־0 עדn-1, ולכלjמ־i + 1עדn-1, הוסף 1 ל־countכאשרnums[i] > nums[j]. - החזר את
count.
def countInversions(nums):
count = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] > nums[j]:
count += 1
return countמיון מיזוג שסופר במהלך המיזוג
האינטואיציה
פצל את הרשימה באמצע. להיפוך יש את שני הערכים בחצי השמאלי, את שניהם בחצי הימני, או ערך אחד בכל צד. קריאה רקורסיבית לכל חצי סופרת את שני הסוגים הראשונים וממיינת את אותו חצי. המיון מזיז ערכים רק בתוך חצי, ולכן כל ערך שמאלי עדיין מופיע לפני כל ערך ימני, והזוגות שחוצים בין החצאים נותרים ללא שינוי.
במיזוג, אם left[i] ≤ right[j], הצב את left[i]: כל ערך ימני שעדיין ממתין הוא לפחות right[j], ולכן הוא אינו יוצר היפוך. אחרת, right[j] קטן מ-left[i], ומכיוון שהחצי השמאלי ממוין, הוא קטן מכל ערך שמאלי שעדיין ממתין. הוסף את מספרם. הצבת הערך השמאלי במקרה של שוויון מונעת מערכים שווים להיכלל.
ב-[5, 3, 8, 1, 4] יש בחצאים היפוך אחד ושני היפוכים. במיזוג [3, 5] עם [1, 4, 8], הערך 1 עובר לפני 3 ו-5, והערך 4 עובר לפני 5: 1 + 2 + 3 = 6.
אלגוריתם
- העתק את
numsוצור מאגר באותו אורך. - כדי למיין ולספור טווח שמכיל פחות מ־2 ערכים, החזר 0.
- אחרת, פצל אותו ב־
midומיין וספור כל חצי. - מזג את החצאים דרך המאגר: אם
left[i] ≤ right[j], קח את הערך השמאלי; אחרת קח את הערך הימני והוסף את מספר הערכים השמאליים שעדיין לא הוכנסו. - העתק את הטווח הממוזג בחזרה והחזר את סכום שלושת הספירות.
def sortAndCount(a, buf, lo, hi):
# Sorts a[lo:hi] and returns the number of inversions inside it.
if hi - lo < 2:
return 0
mid = (lo + hi) // 2
count = sortAndCount(a, buf, lo, mid) + sortAndCount(a, buf, mid, hi)
# Merge the two sorted halves, counting the pairs that cross the middle.
i, j, k = lo, mid, lo
while i < mid and j < hi:
if a[i] <= a[j]:
buf[k] = a[i]
i += 1
else:
# a[j] is smaller than every left value not placed yet: a[i..mid-1].
buf[k] = a[j]
j += 1
count += mid - i
k += 1
while i < mid:
buf[k] = a[i]
i += 1
k += 1
while j < hi:
buf[k] = a[j]
j += 1
k += 1
a[lo:hi] = buf[lo:hi]
return count
def countInversions(nums):
a = list(nums) # sort a copy, not the caller's list
return sortAndCount(a, [0] * len(a), 0, len(a))
מלכודות ומקרי קצה
- הוספת 1 כשממקמים ערך מימין. הוא עובר על פני כל ערכי השמאל שעדיין ממתינים, לכן יש להוסיף את מספרם,
mid - i. - בחירת הערך מימין במקרה של שוויון, כאשר
left[i] < right[j]הוא התנאי לבחירת הצד השמאלי. כך[2, 2, 2, 1]סופר את ערכי ה־2 השווים זה לזה ומחזיר יותר מ־3. השתמשו ב־≤. - ספירה תוך כדי העתקת הערכים שנותרו אחרי שאחד החצאים מתרוקן. לערכי השמאל שנותרו אין ערך מימין אחריהם, וערכי הימין שנותרו כבר הושוו לכל ערכי השמאל.
שאלות נפוצות3
מהי היפוך במערך?
היפוך הוא זוג מיקומים i < j שבו nums[i] > nums[j], כלומר ערך גדול יותר מופיע לפני ערך קטן יותר. ברשימה ממוינת יש 0 היפוכים, וברשימה הפוכה של ערכים ייחודיים יש את המספר הרב ביותר, n(n-1)/2. מספר ההיפוכים שווה למספר החלפות השכנים שמיון בועות מבצע.
מהי סיבוכיות הזמן של ספירת היפוכים באמצעות מיון מיזוג?
זמן של O(n log n) ומקום נוסף של O(n) עבור מאגר המיזוג. בכל אחת מרמות המיזוג, שמספרן log n, עוברים על כל ערך פעם אחת, כלומר בערך 3 × 10^5 צעדים עבור 2 × 10^4 ערכים. הלולאה שעוברת על זוגות אחד־אחד היא O(n²).
האם אפשר לספור היפוכים בלי מיון מיזוג?
כן. עץ פנוויק (עץ בינארי מאונדקס) על דירוגי הערכים עובר על הרשימה פעם אחת, ולכל ערך בודק כמה ערכים קודמים גדולים ממנו, בזמן O(log n) לכל ערך. גם זמן הריצה הכולל הוא O(n log n). עץ חיפוש מאוזן שעוקב אחר הגדלים של תתי־העצים פועל באותו אופן.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def countInversions(nums):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
nums = [5, 3, 8, 1, 4]
הפלט הצפוי
6