这个解决方案的时间复杂度和 space 复杂度是多少？ Question- Top K 频繁元素 (Leetcode-Medium)

Question

 vector<int> topKFrequent(vector<int>& nums, int k) {
    if(k==nums.size())
        return nums;
    map<int,int> mp;
    for(int i=0;i<nums.size();i++)
        mp[nums[i]]++;
    multimap<int,int> m;
    for(auto& it:mp){
        m.insert({it.second,it.first});
    }
    vector<int> ans;
    for (auto itr = m.crbegin(); itr != m.crend(); ++itr){
        ans.push_back(itr->second);
        if(ans.size()==k)
            break;
    }
    return ans;
}

我正在使用 multimap 按 values.I 对地图进行排序不明白如果我使用优先级队列哪个时间复杂度更好？使用 priority_queue 还是使用 multimap？谁能解释一下？

Answer 1

在我看来你没有最优解。

您使用 std::map 而不是 std::unordered_map。在大多数情况下，这将具有更高的复杂性。 std::map具有对数复杂度，std::unordered_map具有平均 constant-time 复杂度。

根本不需要std::multimap。它将增加不必要的 space 和时间复杂度（对数）。 A std::priority_queue 具有常数时间查找，但对数插入。所以，在你的情况下可能比 std::multimap 更好。

最有效的解决方案是使用 std::unordered_map，然后使用 std::partial_sort_copy。复杂度为 O(N·log(min(D,N))，其中 N = std::distance(first, last)，D = std::distance(d_first, d_last) cmp 的应用程序。（取自 CPPReference）。

某种程度上通用的 C++17 示例解决方案可能如下所示：

#include <iostream>
#include <utility>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <iterator>
#include <type_traits>

// Helper for type trait We want to identify an iterable container ----------------------------------------------------
template <typename Container>
auto isIterableHelper(int) -> decltype (
    std::begin(std::declval<Container&>()) != std::end(std::declval<Container&>()),     // begin/end and operator !=
    ++std::declval<decltype(std::begin(std::declval<Container&>()))&>(),                // operator ++
    void(*std::begin(std::declval<Container&>())),                                      // operator*
    void(),                                                                             // Handle potential operator ,
    std::true_type{});
template <typename T>
std::false_type isIterableHelper(...);

// The type trait -----------------------------------------------------------------------------------------------------
template <typename Container>
using is_iterable = decltype(isIterableHelper<Container>(0));

// Some Alias names for later easier reading --------------------------------------------------------------------------
template <typename Container>
using ValueType = std::decay_t<decltype(*std::begin(std::declval<Container&>()))>;
template <typename Container>
using Pair = std::pair<ValueType<Container>, size_t>;
template <typename Container>
using Counter = std::unordered_map<ValueType<Container>, size_t>;

// Function to get the k most frequent elements used  in any Container ------------------------------------------------
template <class Container>
auto topKFrequent(const Container& data, size_t k) {

    if constexpr (is_iterable<Container>::value) {

        // Count all occurences of data
        Counter<Container> counter{};
        for (const auto& d : data) counter[d]++;

        // For storing the top k
        std::vector<Pair<Container>> top(k);

        // Get top k
        std::partial_sort_copy(counter.begin(), counter.end(), top.begin(), top.end(),
            [](const Pair<Container>& p1, const Pair<Container>& p2) { return p1.second > p2.second; });

        return top;
    }
    else
        return data;
}
int main() {
    std::vector testVector{ 1,2,2,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,6,7 };
    for (const auto& p : topKFrequent(testVector, 2)) std::cout << "Value: " << p.first << " \t Count: " << p.second << '\n';
    std::cout << '\n';

    double cStyleArray[] = { 1.1, 2.2, 2.2, 3.3, 3.3, 3.3 };
    for (const auto& p : topKFrequent(cStyleArray, 2)) std::cout << "Value: " << p.first << " \t Count: " << p.second << '\n';
    std::cout << '\n';

    std::string s{ "abbcccddddeeeeeffffffggggggg" };
    for (const auto& p : topKFrequent(s, 2)) std::cout << "Value: " << p.first << " \t Count: " << p.second << '\n';
    std::cout << '\n';

    double value = 12.34;
    std::cout << topKFrequent(value, 2) << "\n";
}

这个解决方案的时间复杂度和 space 复杂度是多少？ Question- Top K 频繁元素 (Leetcode-Medium)

what is the time complexity and space complexity of this solution? Question- Top K Frequent Elements (Leetcode-Medium)

c++

multimap