Majority Element

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

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

קלגיבוב

+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 מופיעים פעם אחת כל אחד.

שאלת המשך

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

פתרון

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

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

האינטואיציה

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

כל חיפוש הוא 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 האחרון הופך שוב למועמד. מעבר יחיד עם שני משתנים דורש זמן 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 כאילו הוא התדירות של הרוב. עבור [8, 8, 1, 1, 8, 1, 8] הוא מסתיים ב-1, בעוד ש-8 מופיע ארבע פעמים.
התחלה עם candidate = nums[0] ועם count = 1, ואז מעבר בלולאה החל מאינדקס 0. האיבר הראשון מצביע פעמיים: ב-[1, 2, 2] הערך של count מסתיים ב-0, ואתה מחזיר 1.

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

מהי סיבוכיות הזמן והמקום של Majority Element?

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

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

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

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

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

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

בדיקה #1

בדיקה #2

ארגומנט

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

הפלט הצפוי