Поддерживать unordered_map, но в то же время нужны самые низкие из отображенных значений на каждом этапе

Question

У меня есть unordered_map<int, int>, который обновляется на каждом шаге for l oop. Но в конце l oop мне также нужно наименьшее из отображенных значений. Поиск минимума в O(n) слишком медленный. Я знаю, что существует контейнер MultiIndex в усилении, но я не могу использовать ускорение. Как проще всего это сделать, используя только STL?

Вопрос:

Для массива A положительных целых чисел вызовите (непрерывный, не обязательно отдельный) подмассив A хорошо, если количество различных целых чисел в этом подмассиве равно K.

(Например, [1,2,3,1,2] имеет 3 разных целых числа: 1, 2 и 3.)

Вернуть количество хороших подмассивов A.

Мой код:

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        int left, right;
        unordered_map<int, int> M;

        for (left = right = 0; right < A.size() && M.size() < K; ++right)
            M[A[right]] = right;
        if (right == A.size())
            return 0;

        int smallest, count;
        smallest = numeric_limits<int>::max();
        for (auto p : M)
            smallest = min(smallest, p.second);
        count = smallest - left + 1;
        for (; right < A.size(); ++right)
        {
            M[A[right]] = right;
            while (M.size() > K)
            {
                if (M[A[left]] == left)
                    M.erase(A[left]);
                ++left;
            }
            smallest = numeric_limits<int>::max();
            for (auto p : M)
                smallest = min(smallest, p.second);
            count += smallest - left + 1;
        }
        return count;
    }
};

Ссылка на вопрос: https://leetcode.com/problems/subarrays-with-k-different-integers/

Answer 1

Я сделал простой класс, чтобы он работал, хотя он далек от совершенства, но его достаточно для ответа на связанный выше вопрос.

class BiMap
{
public:
    void insert(int key, int value)
    {
        auto itr = M.find(key);
        if (itr == M.cend())
            M.emplace(key, S.insert(value).first);
        else
        {
            S.erase(itr->second);
            M[key] = S.insert(value).first;
        }
    }

    void erase(int key)
    {
        auto itr = M.find(key);
        S.erase(itr->second);
        M.erase(itr);
    }

    int operator[] (int key)
    {
        return *M.find(key)->second;
    }

    int size()
    {
        return M.size();
    }

    int minimum()
    {
        return *S.cbegin();
    }

private:
    unordered_map<int, set<int>::const_iterator> M;
    set<int> S;
};

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        int left, right;
        BiMap M;

        for (left = right = 0; right < A.size() && M.size() < K; ++right)
            M.insert(A[right], right);
        if (right == A.size())
            return 0;

        int count = M.minimum() - left + 1;
        for (; right < A.size(); ++right)
        {
            M.insert(A[right], right);
            while (M.size() > K)
            {
                if (M[A[left]] == left)
                    M.erase(A[left]);
                ++left;
            }
            count += M.minimum() - left + 1;
        }
        return count;
    }
};

Answer 2

O(n) не медленный, на самом деле это теоретически самый быстрый способ найти минимум, так как очевидно невозможно найти минимум n элементов без фактического рассмотрения каждого из них.

Вы может обновить минимум во время l oop, что тривиально, если l oop только добавляет новые элементы на карту, но становится намного сложнее, если l oop может изменять существующие элементы (и может увеличить значение минимального до этого момента!), но, в конечном итоге, это также добавляет O (n) объема работы или больше, поэтому с точки зрения сложности это не отличается от выполнения дополнительных l oop в конце ( очевидно, что константа может быть другой - дополнительный l oop может быть медленнее, чем повторное использование исходного l oop, но сложность такая же).

Как вы сказали, есть структуры данных, которые делают более эффективно (O (log n) или даже O (1)) извлекать минимальный элемент, но за счет увеличения сложности поддерживать эту структуру данных во время вставки. Эти структуры данных имеют смысл только в том случае, если вам часто нужно проверять минимальный элемент при вставке или изменении элементов, а не в том случае, если вам нужно знать только минимум только в конце l oop, как вы описали.