Задача: 229. Majority Element II
Сложность: medium

Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз.

Пример:

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

👨‍💻 Алгоритм:

1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика.

2⃣Подсчёт голосов: После определения двух кандидатов, пройдите через массив снова, чтобы посчитать фактическое количество появлений каждого кандидата.

3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат.

😎 Решение:

class Solution {
    func majorityElement(_ nums: [Int]) -> [Int] {
        var count1 = 0, count2 = 0
        var candidate1: Int? = nil
        var candidate2: Int? = nil
        
        for n in nums {
            if let c1 = candidate1, c1 == n {
                count1 += 1
            } else if let c2 = candidate2, c2 == n {
                count2 += 1
            } else if count1 == 0 {
                candidate1 = n
                count1 = 1
            } else if count2 == 0 {
                candidate2 = n
                count2 = 1
            } else {
                count1 -= 1
                count2 -= 1
            }
        }
        
        count1 = 0
        count2 = 0
        
        for n in nums {
            if let c1 = candidate1, c1 == n {
                count1 += 1
            }
            if let c2 = candidate2, c2 == n {
                count2 += 1
            }
        }
        
        var result: [Int] = []
        let n = nums.count
        
        if let c1 = candidate1, count1 > n / 3 {
            result.append(c1)
        }
        if let c2 = candidate2, count2 > n / 3 {
            result.append(c2)
        }
        
        return result
    }
}

Ставь 👍 и забирай 📚 Базу знаний