c++ - 最大值(value)股票，实现细节

Question

我在面试中被问到这样的问题:

给定股票价格:

MS  | 500   
Apl | 1000  
Nefx| 500   
MS  | 500   

每次新库存到来时，我们都必须添加到现有库存中，否则如果是新库存，它就会很糟糕。所以这个结果应该是 MS - 1000, Apl - 1000, Nefs - 500。

我们应该有两个函数:

void add(string, int); // adds new stock  
void display(unsigned n); // displays top n stocks

所以我是这样实现的:

unordered_map<string, int> UM;
void add(string s, int n)
{
    auto iter = M.find(s);
    if(s==M.end())
    { 
        M[str] = n;
    }
    else
    {
        M[str] += n; 
    }
}

void display(unsigned n)
{
    std::map<int,string> M;
    for(auto iter = UM.begin(); iter!=UM.end(); ++iter)
    {
        M.insert(make_pair(iter->second, iter->first));
    }
    for(auto iter = M.rbegin(); iter!=M.rend(); ++iter)
    {
        if(n==0){break;}
        cout<<iter->second<<" "<<iter->first<<endl;
        n--;
    }
}

虽然 add 函数相当有效 O(1) 如果散列是完美的，dislpay 太慢了，O(NlogN) + n。无论我们必须展示多少项目，我们都会操作所有项目。是否有更有效的方法来解决问题，即使它需要更改添加功能？？

Answer 1

add 函数应该是单行 UM[s] += n;。没有其他必要了。

the dislpay is too slow, O(NlogN) + n

您可以将指向 UM 元素的指针复制到 vector 中并执行 std::partial_sort对于 n 个顶级元素，复杂度 O(size*log(n)):

void display(unsigned n) {
    n = std::min<unsigned>(n, UM.size());
    std::vector<std::reference_wrapper<decltype(UM)::value_type>> v(UM.begin(), UM.end());
    std::partial_sort(v.begin(), v.begin() + n, v.end(), [](auto a, auto b) { return a.get().second > b.get().second; });
    for(auto p = v.begin(); n--; ++p)
        std::cout << p->get().second << " " << p->get().first << '\n';
}

---

使用 O(n) 额外存储(而不是上面的 O(N)):

template<class T, class Less>
void insert_sorted_ref(std::vector<T const*>& v, T const& element, Less&& less) {
    auto i = std::lower_bound(v.begin(), v.end(), &element, less);
    if(i == v.end()) {
        if(v.size() < v.capacity())
            v.insert(i, &element);
    }
    else if(less(&element, *i)) {
        if(v.size() == v.capacity())
            v.pop_back();
        v.insert(i, &element);
    }
}

void display(unsigned n) {
    std::vector<decltype(UM)::value_type const*> v;
    v.reserve(std::min<unsigned>(n, UM.size()));
    auto greater = [](auto* a, auto* b) { return a->second > b->second; };
    for(auto const& sn : UM)
        insert_sorted_ref(v, sn, greater);
    for(auto const& p : v)
        std::cout << p->second << " " << p->first << '\n';
}