Снижение временной сложности программы - PullRequest
Новая
       49

Снижение временной сложности программы

0 голосов
/ 28 мая 2020

Я решаю эту практическую задачу, когда дана строка s строчных букв и позиция p, мне нужно распечатать все вхождения буквы в позиции p, которые встречаются перед позицией p .

Например: если строка - «abaa c» и p = 3 (индекс на основе 1), тогда вывод будет 1, потому что «a» встречается один раз перед позицией p.

Там q запросов, каждый из которых дает мне позицию p. Есть ли способ сделать этот код более эффективным?
Я использую хеширование, которое, как мне кажется, довольно эффективно? Есть ли какой-нибудь алгоритм, о котором я не знаю? 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int q;
    cin>>q;
    while(q--)
    {
        int p;
        cin>>p;
        int freq[26] = {0};
        for(int i = 0; i<(p-1); i++)
            freq[s[i]-'a']++;
        cout<<freq[s[p-1]-'a']<<"\n";
    }

}

Ответы [ 3 ]

0 голосов
/ 28 мая 2020

Ваш код в настоящее время делает гораздо больше, чем необходимо. В псевдокоде вы выполняете 

while(q--)
{
    read p
    freq[character] = determine count of any character up to position p
    print freq[character at position p]
}

. Вы повторяете весь процесс подсчета того, как часто каждый символ появляется перед позицией p для каждого отдельного запроса, но затем вы используете информацию только для одного отдельного символа. Это не совсем эффективно. Вместо этого вы должны сделать: 

freq[position] = determine occurences of character at each position
while(q--)
{
    read p
    print freq[p]
}

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

0 голосов
/ 28 мая 2020

Вы можете вычислить решение один раз из строки перед каждым запросом. Итак, каждый запрос в O (1). 

std::vector<std::size_t> build_res(const std::string& s)
{
    std::vector<std::size_t> res;
    int freq[26] = {0};

    for (auto c : s) {
        res.push_back(freq[c - 'a']++); // Assuming a-z contiguous (as in ASCII)
    }
    return res;
}

int main()
{
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    const auto res = build_res(s);
    int q;
    std::cin >> q;
    while (q--)
    {
        int p;
        std::cin >> p;
        std::cout << res[p - 1] << '\n';
    }
}
0 голосов
/ 28 мая 2020

ТОЛЬКО ПОДСКАЗКА

Хитрость заключается в том, чтобы предварительно вычислить ответы сразу после того, как вы прочитаете строку. Вы можете сделать это довольно быстро. Таким образом, за счет сложности памяти вы выиграете от временной сложности. Это может быть выполнено за линейное время до размера строки.

Таким образом, вы сможете дать ответ в следующих запросах за постоянное время.

OFFTOPI C

Эта проблема должна иметь этот код для увеличения скорости ввода-вывода: 

int main()
{
    std::sync_with_stdio(false);
    std::cin.tie(nullptr);
...