Перейти к содержанию

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