[C++] Together using unordered_map and vector to get highest efficiency


  • 0
    S

    An unordered_map is fast in searching and inserting, but may be slow at iterating. So I used an unordered_map index and a vector stats together to enhance efficiency. Is that good practice?
    Also, is there any way to find the largest k elements better than using std::nth_element?
    Thanks!

    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, vector<int>::size_type> index;
            struct stat_type {
                int val;
                vector<int>::size_type count;
                stat_type(int val) : val(val), count(1) {}
                static bool larger(stat_type &x, stat_type &y) {return x.count > y.count; }
            };
            vector<stat_type> stats;
            vector<int>::size_type next = 0;
            for (auto &num : nums) {
                auto id = index.find(num);
                if (id != index.end()) {
                    stats[id->second].count += 1;
                } else {
                    stats.push_back(stat_type(num));
                    index[num] = next++;
                }
            }
            nth_element(stats.begin(), stats.begin() + k - 1, stats.end(), stat_type::larger);
            vector<int> result(k);
            for (int i = 0; i < k; i++) 
                result[i] = stats[i].val;
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.