Majority Element

🇷🇺 Название: Мажоритарный элемент
LeetCode: majority-element
Временная сложность: O(n)
Пространственная сложность: O(1)

Решение

from typing import List  


class Solution:  
    def majorityElement(self, nums: List[int]) -> int:  
        count = 0  
        candidate = None  

        for num in nums:  
            if count == 0:  
                candidate = num  
            if num == candidate:  
                count += 1  
            else:  
                count -= 1

        return candidate

🇺🇸 Условие

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

🇷🇺 Условие

Примеры

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

{
  "examples": [
    {
      "input": {
        "nums": [3,2,3]
      },
      "output": 3
    },
    {
      "input": {
        "nums": [2,2,1,1,1,2,2]
      },
      "output": 2
    }
  ]
}

Ограничения

• n == nums.length
• \(1 \leq n \leq 5 * 10^4\)
• \(-10^9 \leq nums[i] \leq 10^9\)

Потребление ресурсов

⏱ Time complexity: O(n)

• Используется алгоритм Бойера–Мура (Boyer–Moore Voting Algorithm).
• Один проход по массиву nums, без вложенных циклов или сортировки.

Итог: O(n)

🧠 Space complexity: O(1)

• Алгоритм работает в константной памяти, без использования дополнительных структур данных.
• Только две переменные: candidate и count.

Итог: O(1)

easy array hash-table divide-and-conquer sorting counting

---

Metadata

• title_rus: Мажоритарный элемент
• difficulty: Easy
• leetcode_url: https://leetcode.com/problems/majority-element/
• topics: ['Array', 'Hash Table', 'Divide and Conquer', 'Sorting', 'Counting']
• time: O(n)
• space: O(1)
• grind75: True
• tags: ['Array', 'Counting', 'Divide and Conquer', 'Easy', 'Hash Table', 'Sorting', 'problem']
• git_revision_date_localized: 5 июля 2025 г.
• git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_revision_date_localized_tag:
• git_revision_date_localized_raw_date: 5 июля 2025 г.
• git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_revision_date_localized_raw_iso_date: 2025-07-05
• git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_revision_date_localized_raw_timeago:
• git_revision_date_localized_raw_custom: 05. июля 2025
• git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_site_revision_date_localized_tag:
• git_site_revision_date_localized: 5 июля 2025 г.
• git_site_revision_date_localized_raw_date: 5 июля 2025 г.
• git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_site_revision_date_localized_raw_iso_date: 2025-07-05
• git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_site_revision_date_localized_raw_timeago:
• git_site_revision_date_localized_raw_custom: 05. июля 2025