Top K Frequent Elements
נתון לך מערך של מספרים שלמים nums ומספר שלם k. החזר את k הערכים שמופיעים בתדירות הגבוהה ביותר ב־nums, כשהערך שמופיע בתדירות הגבוהה ביותר מופיע ראשון. כאשר שני ערכים מופיעים באותו מספר פעמים, הערך הקטן יותר מופיע ראשון.
כל ערך מופיע פעם אחת בתשובה, בלי קשר למספר הפעמים שהוא מופיע ב־nums, ו־k לעולם אינו גדול ממספר הערכים השונים.
פונקציה
- numsinteger-array
- הערכים שיש לספור
- kinteger
- כמה ערכים להחזיר
- מחזירהinteger-array
- k הערכים השכיחים ביותר, לפי סדר שכיחות יורד, ובמקרה של תיקו — הערך הקטן יותר קודם
אילוצים
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ k, ו-kהוא לכל היותר מספר הערכים הייחודיים ב-nums.
דוגמאות
- קלט
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- פלט
- [4, 1]
- הסבר
4מופיע ארבע פעמים,1שלוש פעמים, ו־2ו־3פעם אחת כל אחד. שני הערכים הנפוצים ביותר הם4, ואז1.
- קלט
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- פלט
- [-2, 5]
- הסבר
-2,5ו־7מופיעים כל אחד פעמיים, ו־9פעם אחת. שלושה ערכים נמצאים בשוויון במקום הראשון, ולכן שני הערכים הקטנים יותר,-2ו־5, הם התשובה.
- קלט
- nums = [8]k = 1
- פלט
- [8]
- הסבר
- יש ערך אחד, ולכן הוא השכיח ביותר.
+16 בדיקות נסתרות בשליחה
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
התחילו בבדיקה של תדירות ההופעה של כל ערך. איזו מבנה נתונים ממפה ערך למספר הפעמים שהוא מופיע במעבר אחד?
כשיש לך את הספירות, צריך למצוא את
kהערכים הטובים ביותר לפי סדר אחד: קודם הערך עם הספירה הגבוהה יותר, ובמקרה של שוויון — הערך הקטן יותר. אפשר למיין את כל הערכים השונים. ערימת מינימום בגודלkשומרת רק את הערכים שעדיין יכולים להיכלל בתשובה.ספירה היא מספר שלם מ־1 עד
n. צרו דלי אחד לכל ספירה, כשהדליcמכיל את הערכים שמופיעים בדיוקcפעמים, וקראו את הדליים מהספירה הגבוהה ביותר לנמוכה ביותר. מלאו את הדליים על ידי מעבר על הערכים מהקטן לגדול, וכך כל דלי כבר מסודר לפי סדר שובר השוויון.
פתרון
הספירה היא החלק המהיר: מעבר אחד עם מפת גיבוב נותן את מספר ההופעות של כל ערך. השאלה האמיתית היא איך לבחור את k הערכים הטובים ביותר בלי לעשות יותר עבודה מהנדרש. מיון כל d הערכים השונים לפי מספר ההופעות עולה O(d log d), ערימת מינימום בגודל k מורידה את העלות ל־O(d log k), ומכיוון שמספר ההופעות הוא מספר שלם מ־1 עד n, מיון דליים מסדר את הערכים לפי מספר ההופעות ללא השוואות כלל.
לספור, ואז למיין לפי הספירה
האינטואיציה
ספרו תחילה. מעבר אחד עם מפת גיבוב מערך לספירה הופך את [4, 1, 4, 2, 1, 4, 3, 1, 4] ל-4 → 4, 1 → 3, 2 → 1, 3 → 1.
לאחר מכן סדרו את הערכים השונים לפי סדר התשובה: הספירה הגבוהה יותר קודם, ובמקרה של ספירות שוות הערך הקטן יותר קודם. הגדירו למיון בדיוק את ההשוואה הזאת, כשהספירה היא המפתח הראשון והערך הוא המפתח השני, ו-k האיברים הראשונים ברשימה הממוינת הם התשובה. כאן הסדר הוא 4, 1, 2, 3, ו-k = 2 משאיר את 4 ואת 1.
הספירה עולה O(n). מיון d הערכים השונים עולה O(d log d), ולכל היותר O(n log n) כאשר כל הערכים שונים: 10^4 ערכים מצריכים בערך 1.3 × 10^5 השוואות, וזה מהיר. הבזבוז הוא שהמיון מסדר את כל הערכים, אף שרק k הראשונים חשובים.
אלגוריתם
- ספרו כל ערך במפת גיבוב.
- הכניסו את הערכים הייחודיים לרשימה.
- מיינו את הרשימה לפי מספר ההופעות בסדר יורד, ובמקרה של מספר הופעות שווה, לפי הערך בסדר עולה.
- החזירו את
kהערכים הראשונים.
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Most frequent first; equal counts put the smaller value first.
ordered = sorted(counts, key=lambda value: (-counts[value], value))
return ordered[:k]שומרים את k הטובים ביותר בערימת מינימום
האינטואיציה
צריך רק את k הערכים הטובים ביותר, לכן שומרים רק k מועמדים. עבור כל ערך חדש, השאלה היא אם הוא טוב יותר מהמועמד החלש ביותר ששומרים, כאשר חלש יותר פירושו ספירה נמוכה יותר, או אותה ספירה וערך גדול יותר. ערימת מינימום שממוינת לפי הכלל הזה משאירה את המועמד החלש ביותר בראש, שם אפשר לקרוא אותו ב־O(1) ולהחליף אותו ב־O(log k).
עוברים על הערכים השונים. כל עוד יש בערימה פחות מ־k ערכים, מוסיפים את הערך. לאחר מכן, ערך שטוב יותר מהערך שבראש הערימה מחליף אותו, וערך שאינו טוב יותר נזרק, כי כבר נשמרו k ערכים טובים יותר. בשימוש בערימה מספרייה, הקוד קצר יותר אם מוסיפים כל ערך ומסירים ערך אחד בכל פעם שהערימה גדלה מעבר ל־k, וכך נשמרים אותם k ערכים.
בסוף הערימה מכילה את התשובה, אבל לא לפי סדר התשובה: ערימה ממוינת רק באופן חלקי. הסרה מהערימה מחזירה קודם את הערך החלש ביותר, לכן יש לכתוב את התשובה מהמיקום האחרון לאחור, עד למיקום הראשון.
כל אחד מ־d הערכים השונים דורש לכל היותר פעולת ערימה אחת על k איברים, ולכן הבחירה דורשת O(d log k). זה מהיר יותר ממיון כאשר k קטן בהרבה מ־d, למשל בבחירת 10 הערכים המובילים מתוך 8000 ערכים שונים.
אלגוריתם
- סופרים כל ערך במפת גיבוב.
- עבור כל ערך ייחודי, דוחפים אותו כל עוד הערימה מכילה פחות מ־
kערכים. - כשהערימה מלאה, משווים את הערך לראש הערימה, הערך החלש ביותר שנשמר. אם הערך החדש חזק יותר, שמים אותו בראש ומסננים אותו כלפי מטה.
- מוציאים ערכים מהערימה
kפעמים, וכותבים כל ערך בתשובה מהאחרון לראשון.
import heapq
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Entries are (count, -value). heapq keeps the smallest entry on top, which is
# the weakest value kept: the lowest count, and on a tie the larger value.
heap = []
for value, count in counts.items():
heapq.heappush(heap, (count, -value))
if len(heap) > k:
heapq.heappop(heap)
# Pops come out weakest first, so fill the answer from the back.
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = -heapq.heappop(heap)[1]
return resultספירה, ואז מיון לפי ספירה באמצעות דליים
האינטואיציה
ספירה אינה סתם מספר: היא מספר שלם מ־1 עד n. כך אפשר להשתמש במיון דליים. יוצרים דלי לכל ספירה; בדלי c נמצאים הערכים שמופיעים בדיוק c פעמים, וקוראים את הדליים מדלי n ומטה. הערכים מתקבלים לפי סדר התדירות, מהתדיר ביותר לפחות תדיר, ולעולם אין צורך להשוות בין שתי ספירות.
כלל השוויון דורש עוד דבר אחד: בתוך דלי, הערך הקטן יותר חייב להופיע ראשון. הערכים נמצאים בין -10^4 ל־10^4, ולכן מערך של R = 2 × 10^4 + 1 מונים יכול לבצע את הספירה, כאשר הערך v נמצא באינדקס v + 10^4. עוברים על המערך הזה מהערך הקטן ביותר לגדול ביותר, ומוסיפים כל ערך לדלי של הספירה שלו. כל דלי מתמלא בסדר עולה, שהוא סדר השוויון, ולכן אין צורך למיין דבר.
עבור [5, -2, 7, -2, 7, 5, 9], המעבר מכניס את -2, 5, 7 לדלי 2, בסדר הזה, ואת 9 לדלי 1. כשקוראים מהדלי 7 ומטה, הדלי הראשון שמכיל ערכים הוא דלי 2, ו־k = 2 בוחר את -2 ואת 5.
העבודה כוללת מעבר אחד על nums, מעבר אחד על R המונים ומעבר אחד על הדליים, ובסך הכול O(n + R): זמן ליניארי עבור טווח ערכים קבוע. אם משתמשים במפת גיבוב במקום במערך הספירה, הספירה נשארת ליניארית, אבל הדליים מתמלאים בסדר המפה, ולכן יהיה צורך למיין כל אחד מהם כדי לציית לכלל השוויון.
אלגוריתם
- ספור כל ערך במערך, באינדקס
value + 10^4. - צור דליים מ־1 עד
n, רשימה אחת לכל ספירה אפשרית. - עבור על מערך הספירה מהערך הקטן ביותר לגדול ביותר, והוסף כל ערך שמופיע לדלי של הספירה שלו.
- קרא את הדליים מספירה
nועד 1, וקח ערכים עד שיהיו לךk.
def topKFrequent(nums, k):
OFFSET = 10000 # values run from -10^4 to 10^4
counts = [0] * (2 * OFFSET + 1)
for x in nums:
counts[x + OFFSET] += 1
# buckets[c] lists the values that occur exactly c times. Walking the
# values from smallest to largest fills every bucket in ascending order.
buckets = [[] for _ in range(len(nums) + 1)]
for i, c in enumerate(counts):
if c > 0:
buckets[c].append(i - OFFSET)
# Read the buckets from the highest count down until k values are taken.
result = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
result.append(value)
if len(result) == k:
return result
return result
מלכודות ומקרי קצה
הספירה כמעט אף פעם לא שגויה. סדר התשובה הוא זה ששגוי.
- שבירת שוויון לפי סדר הופעה ראשון או לפי סדר של מפת גיבוב. בדוגמה השנייה,
-2,5ו-7מופיעים כולם פעמיים, ורק הכלל שלפיו בוחרים בערך הקטן יותר הופך את[-2, 5]לתשובה הנכונה היחידה. - החזרת המערך של הערימה כפי שהוא. ערימה מסודרת רק חלקית, והערך שבראשה הוא הערך החלש ביותר — זה שצריך להופיע אחרון.
- היפוך כלל השוויון של הערימה. מבין שני ערכים עם אותה ספירה, הגדול יותר חלש יותר, ולכן ערימת מינימום לפי
(count, value)מוציאה את הערך הלא נכון. השתמשו ב-(count, -value)או בהשוואה שנכתבה בהתאם לכלל. - יצירת מספר דליים ששווה רק למספר הערכים השונים. ערך אחד יכול להופיע
nפעמים, כמו ב-[3, 3, 3, 3], ולכן חייב להיות דליn. - ב-Java, השוואת שתי ספירות מסוג
Integerבאמצעות!=. כך משווים הפניות, וההשוואה נכשלת כשהספירות עולות על 127. הסירו תחילה את העטיפה שלהן והמירו אותן ל-int. - לקיחת דלי שלם בסוף. עצרו ברגע שיש לכם
kערכים, גם אם זה באמצע דלי.
שאלות נפוצות4
מהי סיבוכיות הזמן של Top K Frequent Elements?
הספירה דורשת O(n). בחירת k הערכים המובילים דורשת לאחר מכן O(d log d) עם מיון של d הערכים הייחודיים, O(d log k) עם ערימת מינימום בגודל k, ו־O(n) בתוספת מעבר אחד על טווח הערכים באמצעות מיון דליים. מכיוון ש־d יכול להגיע עד n, במקרה הגרוע המיון דורש O(n log n), ומיון דליים הוא ליניארי.
האם אפשר לפתור את בעיית K האיברים השכיחים ביותר בזמן O(n)?
כן, באמצעות מיון דליים. הספירות הן מספרים שלמים מ־1 עד n, ולכן כל ערך נכנס לדלי המתאים לספירה שלו, וקריאת הדליים מהספירה הגבוהה ביותר לנמוכה ביותר מציגה את הערכים לפי תדירות, ללא מיון השוואתי. גם Quickselect על הספירות הוא O(n) בממוצע, אבל במקרה הגרוע הסיבוכיות שלו ריבועית.
למה להשתמש בערימת מינימום ולא בערימת מקסימום?
ערימת max-heap של כל הערכים d מתאימה גם היא: בונים אותה ב־O(d) ושולפים ממנה k פעמים, בסך הכול O(d + k log d). ערימת min-heap בגודל k מכילה רק k איברים ומתאימה לערכים שמגיעים בזה אחר זה, כי האיבר העליון שלה הוא המועמד להסרה. המחיר הוא שהתשובה מתקבלת בסדר הפוך, ולכן ממלאים את התוצאה מהסוף.
איך שוברים שוויון ב־Top K Frequent Elements?
בחרו כלל אחד והחילו אותו בכל מקום; כאן, כשיש ספירות שוות, הערך הקטן יותר מופיע ראשון, וכך התשובה ייחודית. במיון, השוו בין הספירות ואז בין הערכים. בערימה, מבין שני ערכים עם ספירות שוות, הערך הגדול יותר הוא החלש יותר. במיון דלי, מלאו את הדליים בסדר עולה לפי הערך, וכל דלי כבר מסודר לפי כללי שבירת השוויון.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def topKFrequent(nums, k):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
צפוי
[4, 1]