169. Majority Element

Задача

Дан массив nums размера n . Верните элемент большинства (majority element).

Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Вы можете считать, что элемент большинства всегда существует в массиве.

Примеры

Пример 1

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

Пример 2

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

Решение

Решение

/**
 * Временная сложность: O(N log N) - из-за сортировки
 * Пространственная сложность: O(1) или O(N) (зависит от реализации sort)
 */
var majorityElement = function(nums) {
    nums.sort((a, b) => a - b);
    return nums[Math.floor(nums.length / 2)];
};

Решение 2 (HashMap)

/**
 * Временная сложность: O(N)
 * Пространственная сложность: O(N) - храним все уникальные элементы
 */
var majorityElement = function(nums) {
    const counts = {};
    const limit = nums.length / 2;
 
    for (const num of nums) {
        counts[num] = (counts[num] || 0) + 1;
        if (counts[num] > limit) {
            return num;
        }
    }
};

Решение 3 (Алгоритм голосования Бойера-Мура (Boyer-Moore Voting Algorithm).)

/**
 * Временная сложность: O(N)
 * Пространственная сложность: O(1) - всего две переменные!
 */
var majorityElement = function(nums) {
    let count = 0;
    let candidate = null;
 
    for (const num of nums) {
        if (count === 0) {
            candidate = num;
        }
 
        // Если совпало - добавляем голос (+1), если нет - отнимаем (-1)
        count += (num === candidate) ? 1 : -1;
    }
 
    return candidate;
};