Majority Element

+10

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

פונקציה

majorityElement(nums: integer-array) → integer

numsinteger-array: מערך המספרים השלמים, שבו ערך אחד תופס יותר ממחציתו
מחזירהinteger: הערך שמופיע יותר מ־n / 2 פעמים

אילוצים

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
ערך אחד מופיע יותר מ־nums.length / 2 פעמים.

דוגמאות

קלט: nums = [3, 9, 3, 3, 4]
פלט: 3
הסבר: 3 מופיע שלוש פעמים בחמישה איברים. שלוש גדול מ־5 / 2 = 2.5, ו־9 ו־4 מופיעים פעם אחת כל אחד.

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

שאלת המשך

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

פתרון

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

ספירה באמצעות מפת גיבוב

האינטואיציה

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

עבור [3, 9, 3, 3, 4], המונה של 3 מגיע ל־1 באינדקס 0, ל־2 באינדקס 2 ול־3 באינדקס 3. שלושה עותקים מתוך חמישה הם יותר מ־2.5, לכן מחזירים 3 בלי לקרוא את האיבר האחרון.

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

אלגוריתם

צרו מפה ריקה מערך לספירה.
עבור כל איבר x, הוסיפו 1 לספירה של x.
אם הספירה הזאת כפול 2 גדולה מאורך המערך, החזירו את x.

def majorityElement(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] * 2 > len(nums):
            return x

הצבעת בוייר-מור

האינטואיציה

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

למה הערך שנותר בסוף הוא הרוב: כל ביטול מסיר שני ערכים שונים, ולכן מסיר לכל היותר עותק אחד של ערך הרוב. נניח שערך הרוב מופיע m פעמים. יש רק n - m איברים אחרים, פחות מ־m, ולכן הם לא יכולים לבטל את כל העותקים. כל הקולות שנותרו בסוף שייכים למועמד הסופי, ואחד מהם הוא עותק של ערך הרוב, ולכן המועמד הוא ערך הרוב.

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

אלגוריתם

הגדר את candidate לאיבר הראשון ואת count ל־0.
עבור כל איבר x, אם count הוא 0, הגדר את x כמועמד.
אם x שווה למועמד, הוסף 1 ל־count. אחרת, הפחת 1.
אחרי האיבר האחרון, החזר את candidate.

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for x in nums:
        if count == 0:
            candidate = x  # the old candidate's votes are used up
        if x == candidate:
            count += 1
        else:
            count -= 1  # x and one copy of the candidate cancel out
    return candidate

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

רוב התשובות השגויות נובעות מקו הגבול של חצי, או מפרשנות יתר של המונה.

״יותר מחצי״ פירושו גדול ממש מחצי. count >= n / 2 מקבל 2 עותקים מתוך 4, וזה לא רוב. השווה בין count * 2 > n, וכך עיגול לא יכול להפריע.
הערך הסופי של count באלגוריתם Boyer-Moore אינו מציין כמה פעמים הרוב מופיע. עבור [8, 8, 1, 1, 8, 1, 8] הוא מסתיים בערך 1, בעוד ש-8 מופיע ארבע פעמים.
התחלה עם candidate = nums[0] ועם count = 1 עובדת רק אם הלולאה מתחילה אחר כך באינדקס 1. אם מתחילים אותה באינדקס 0, האיבר הראשון מצביע פעמיים: עבור [1, 2, 2] המונה מסתיים בערך 0 ואתה מחזיר 1.
אלגוריתם Boyer-Moore מסתמך על ההבטחה. עבור [1, 2, 3], שאין בו רוב, הוא עדיין מחזיר 3. אם ייתכן שאין רוב בקלט, ספור את המועמד במעבר שני לפני שתסמוך עליו.

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

מהו אלגוריתם ההצבעה של Boyer-Moore?

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

מהי סיבוכיות הזמן והמקום של אלמנט הרוב?

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

האם אפשר לפתור את בעיית הרוב באמצעות מיון?

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

מה אם ייתכן שאין במערך איבר רוב?

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

קלט

nums = [3, 9, 3, 3, 4]

צפוי