Поиск количества вхождений элементов в отсортированном массиве для множества запросов

Question

Условие:

Дан отсортированный целочисленный массив, содержащий повторяющиеся элементы и состоящий из n элементов.

Необходимо для каждого из m запросов найти, какое количество раз в данном массиве встречается заданное значение k.

Входные данные:

В первой строке входного файла дано значение n(1<=n<=100000) - количество элементов массива

Во второй строке входного файла дан сам массив.

В третьей строке входного файла дано значение m(1<=m<=100000) – количество запросов.

В каждой из следующих m строк дано единственное число – значение k (для каждого запроса значение k может быть как различно, так и одинаково).

Выходные данные:

Для каждого запроса в выходной файл должно быть выведено единственное значение - количество вхождений числа k в массив, если элемента k в массиве нет, то необходимо вывести - «Not found».

Значение для каждого нового запроса должно быть выведено в отдельной строке.

Ограничения:

Время — 1000 ms

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n, x;
    cin >> n;
    int mas[n];
    for (int i = 0; i < n; i++) cin >> mas[i];
    string s;
    cin >> x;

    for (int i = 0; i < x; i++)
    {
        int ch = 0;
        int t; cin >> t;
        for (int j = 0; j < n; j++)
        {
            if (mas[j] == t) ch++;
        }
        if (ch != 0)
        {
            s += to_string(ch);
            s.append(" ");
        }
        else s.append("N ");
    }
    for (int i = 0; i < size(s); i++)
    {
        if (s[i] != 'N')
        {
            while (s[i] != ' ')
            {
                cout << s[i];
                i++;
            }
            cout << endl;
        }
        else
        {
            cout << "Not found" << endl;
            i++;
        }
    }

    return 0;
}

Answer 1

Сосчитать значения в counts, отвечать на запросы:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> counts;

    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        int v;
        std::cin >> v;
        counts[v] += 1;
    }

    int m;
    std::cin >> m;
    for (int j = 0; j < m; ++j) {
        int v;
        std::cin >> v;
        auto it = counts.find(v);
        if (it == counts.end()) {
            std::cout << "Not found\n";
        } else {
            std::cout << it->second << '\n';
        }
    }
}

Я упустил что значения на входе упорядочены. Тогда можно решить задачу по-другому:

#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> a;

    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        int v;
        std::cin >> v;
        a.push_back(v);
    }

    int m;
    std::cin >> m;
    for (int j = 0; j < m; ++j) {
        int v;
        std::cin >> v;
        auto range = std::equal_range(a.begin(), a.end(), v);
        auto c = range.second - range.first;
        if (c == 0) {
            std::cout << "Not found\n";
        } else {
            std::cout << c << '\n';
        }
    }
}

Answer 2

Вариант с хеш-таблицей, как в ответе выше - правильное и адекватное решение, которое работает даже не в отсортированном случае. Кроме того, быстрее никак не получится. Однако, если по какой-то причине нужно решить без хеш-таблицы, можно делать это бинарным поиском поиском. Ищем самое левое и самое правое вхождение нужного элемента (происходит это за O(2log(n)) = O(log(n)), т.к. массив отсортирован). Итоговая временная сложность будет O(m*log(n)).

БЛОГ НА HUSL

Поиск количества вхождений элементов в отсортированном массиве для множества запросов

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