Is my solution O(n)? If it is, why it is so slow. BTW I didn't similar solution here.


  • 0
    M

    Idea is simple, just put the number to their times they appear. For example. log[0] stores all the number that appear once. log[3] stores all number that appear 4 times etc. The maximum times of an element could've appeared is n times where n is size of the array. I put time complexity analysis on each function. This should be O(n). Please correct me if I'm wrong

    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            vector<list<int>> log (nums.size(), list<int>());
            unordered_map<int, int> counter;
            unordered_map<int, list<int>::iterator> pointer;
            
            for (int i = 0; i < nums.size(); i++) {
                int current = nums[i];
                if (counter[current]) {
                    int previousCount = counter[current];
                    log[previousCount-1].erase(pointer[current]);   //O(1)
                    
                    counter[current] ++;
                    log[previousCount].insert(log[previousCount].begin(), current);     //O(1)
                    pointer[current] = log[previousCount].begin();
                }
                else {
                    counter[current] = 1;
                    log[0].insert(log[0].begin(), current);     //O(1)
                    pointer[current] = log[0].begin();
                }
            }
            vector<int> result;
            
            //O(k) while k is at most n:
            for (int i = nums.size()-1; i >= 0; i--) {
                if (result.size() >= k) {
                    break;
                }
                if (!log[i].empty()) {
                    for (int num : log[i]) {
                        result.push_back(num);
                    }
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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