降低程序的时间复杂度

Question

我正在做这个练习题，给定一个小写字母的字符串s，以及一个位置p，我必须在位置p打印所有在位置p之前出现的字母。

例如：如果字符串是"abaac"并且p = 3(基于1的索引(，则输出为1，因为"a"在位置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";
}
}

Answer 1

仅提示

这里的诀窍是在读取字符串后预先计算答案。你可以很快做到这一点。 因此，作为记忆复杂性的交换，您将获得时间复杂性。 这可以在线性时间内完成字符串大小。

这样，您将能够在恒定时间内在以下查询中提供答案。

题外话

这个问题应该有以下代码来提高 IO 速度：

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

Answer 2

可以在每次查询之前从字符串中计算一次解决方案。 所以 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';
}
}

Answer 3

您的代码当前执行的操作远远超出了必要的范围。在伪代码中，你执行

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]
}

第一部分可以通过遍历输入字符串一次来完成，然后对于每个查询，您只需从表中查找结果。