Обобщенный случай алгоритма Бойера и Мура, для нажождения мажорирующего элемента

Question

Пытаюсь реализовать обобщенный алгоритма Бойера и Мура. Задача : требуется в массиве длиной N найти элементы, встречающийся более N/K раз. Вот мой код:

vector<int> majorityElement(vector<int> &nums, int k){
    cout <<"in fun\n";
    map<int,int> candidates;
    vector<int> ans;
    for(int i = 0; i < nums.size(); i++){
        cout << "here " << i << endl;
        if (candidates.count(nums[i]))
            candidates[nums[i]]++;
        else{
            if (candidates.size() < (k - 1))
                candidates[nums[i]] = 1;
            else{
                for (auto it = candidates.begin(); it != candidates.end(); ++it){
                    candidates[it->first]--;
                    if (candidates[it->first] == 0){
                        candidates.erase(it);
                    }
                }
            }
        }
    }

    for (auto it = candidates.begin(); it != candidates.end(); ++it){
        candidates[it->first] = 0;
    }

    for (int i = 0; i < nums.size(); i++){
        if (candidates.count(nums[i]))
            candidates[nums[i]]++;
    }

    for (auto it = candidates.begin(); it != candidates.end(); ++it){
        if (candidates[it->first] > (nums.size() / k))
            ans.push_back(it->first);
    }
    return ans;

}

На тесте: 7 3 1 1 1 2 5 6 7 Программа ломается полностью, при обработке числа 5. Вот тут есть описание алгоритмы с псевдокодом

Answer 1

При удалении элемента итератор инвалидируется, его больше нельзя использовать (инкрементировать и т.д.). Но метод erase возвращает следующий валидный итератор.

Поэтому замените это

for (auto it = candidates.begin(); it != candidates.end(); ++it) {
    candidates[it->first]--;
    if (candidates[it->first] == 0) {
        candidates.erase(it);
    }
}

на это

for (auto it = candidates.begin(); it != candidates.end();) {
    if (--(it->second) == 0) {
        it = candidates.erase(it);
    }
    else ++it;
}

Также стоит заменить map на unordered_map

БЛОГ НА HUSL

Обобщенный случай алгоритма Бойера и Мура, для нажождения мажорирующего элемента

Ответы (1 шт):