Обзор функции sockMerchant. Как улучшить её временную сложность?

Question

int sockMerchant(int& n, vector<int>& ar) {
    set<int> s;
    for(int i{}; i < n; ++i){
        s.insert(ar[i]);
    }

    int pairs{};

    for(auto it = s.begin(); it != s.end(); ++it){
        int k{};
        for(int i{}; i < n; ++i){
            if(ar[i] == *it){
               k++;
            }
        }

        pairs += (k / 2);
    }
    return pairs;
}

Answer 1

Заполнение сета O(n*lb(n))
Проход по сету O(n)
- Проход по массиву O(n)

Получается O(n**2)

Улучшить - вместо сета увеличивать кличество в map - будет O(n*lb(n))

map <int, int> s;

for (int i{}; i < n; ++i)
  ++s[ar[i]];

int pairs{};

for (auto p : s)
  pairs += p.second / 2;

PS: Что-то алгоритм подозрительный.

БЛОГ НА HUSL

Обзор функции sockMerchant. Как улучшить её временную сложность?

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