C++，多重集，时间复杂度

Question

#include<bits/stdc++.h>

int main()
{
    int n;
    std::cin>>n;
    char st[n];
    getchar();
    for (int i=0; i<n; ++i)
        st[i]=getchar();
    std::multiset<char> s;
    int pos1=0,pos2=n-1;
    for (char c:st) s.insert(c);
    for (int i=0; i<n; ++i) {
        if (s.count(st[i])==1) {
            pos1=i;
            break;
        } else s.erase(s.find(st[i]));
    }
    for (int i=n-1; i>=0; --i) {
        if (s.count(st[i])==1) {
            pos2=i;
            break;
        } else s.erase(s.find(st[i]));
    }
    std::cout<<pos2-pos1+1;
}

我刚把这段代码提交给CodeForces系统，它没有通过TL（2s），我不知道为什么，因为n constrain是10^5。我的代码使用 O(nlogn)。你们能帮帮我吗？谢谢<3<3。 Link 这里的问题：http://codeforces.com/problemset/problem/701/C

Answer 1

的确，你的算法是 O(nlogn) 但这不是保证不超过时间限制。请记住，大 O 复杂性的乘法常数可能太大而无法将其保持在特定时间限制内。

您使用 multiset 只是为了统计每种口袋妖怪的数量。您会浪费很多时间从该多重集中擦除并从中重新计数。你可以做的比 multiset:

快得多

通过使用 map 来保持每种类型的计数并更新它

更好的是，由于 pokemon 类型以单个字符编码，您可以使用 256 个元素的数组来跟踪计数。这样您就可以避免多重集（和映射）的 "log(n)" 复杂性。这是代码的重构版本，应该运行快得多，而且运行s in O(n)。

int main() { 诠释 n; std::cin >> n; std::vector st(n); std::array 计数； // 如果我们有更大的类型集，我们也可以使用映射...

// the way you read the input can also be speeded-up,
// but I want to focus on speeding up the algorithm
getchar();
for (int i=0; i<n; ++i) {
    st[i]=getchar(); ++count[st[i]];
}

int pos1=0,pos2=n-1;
for (int i=0; i < n; ++i) {
    if (count[st[i]] == 1) {
        pos1 = i;
        break;
    } else --count[st[i]];
}
for (int i=n-1; i>=0; --i) {
    if (s.count(st[i])==1) {
        pos2=i;
        break;
    } else --count[st[i]];
}
std::cout<<pos2-pos1+1;

}

C++，多重集，时间复杂度

C++, multiset, Time complexity

c++

time-complexity

multiset