Finally accepted using two unordered map with complexity O(n)


  • 4
    Z

    I use two maps to keep the numbers from ascending and descending order. In fact, I think these two maps can be merged into one. But that would be much more difficult to understand

    class Solution {
    public:
        int longestConsecutive(vector<int> &num) {
            unordered_map<int,int> seq;     //lower to higher
            unordered_map<int,int> seq2;    //higher to lower
            int maxlen = 0;
            for(int i=0;i<num.size();i++){
                unordered_map<int,int>::iterator it;
                unordered_map<int,int>::iterator it2;
                it = seq.find(num[i]);
                it2 = seq2.find(num[i]);
                if(it != seq.end() || it2 != seq2.end()){
                    continue;
                }
                it = seq.find(num[i]+1);    //find if num[i] can be lower
                it2 = seq2.find(num[i]-1);  //find if num[i] can be higher
                if(it != seq.end() && it2 != seq2.end()){ //if there are two sequences that can be merged together
                    int high = it->second;
                    int low = it2->second;
                    seq.erase(it);
                    seq.erase(low);
                    seq2.erase(high);
                    seq2.erase(it2);
                    seq.insert(pair<int,int>(low,high));
                    seq2.insert(pair<int,int>(high,low));
                    maxlen = maxlen > high-low+1 ? maxlen : high-low+1;
                }
                else if(it != seq.end()){
                    int high = it->second;
                    seq.erase(it);
                    seq2.erase(high);
                    seq.insert(pair<int,int>(num[i],high));
                    seq2.insert(pair<int,int>(high,num[i]));
                    maxlen = maxlen > high-num[i]+1 ? maxlen : high-num[i]+1;
                }
                else if(it2 != seq2.end()){
                    int low = it2->second;
                    seq2.erase(it2);
                    seq.erase(low);
                    seq.insert(pair<int,int>(low,num[i]));
                    seq2.insert(pair<int,int>(num[i],low));
                    maxlen = maxlen > num[i]-low+1 ? maxlen : num[i]-low+1;
                }
                else{
                    seq.insert(pair<int,int>(num[i],num[i]));
                    seq2.insert(pair<int,int>(num[i],num[i]));
                    maxlen = maxlen > 1 ? maxlen : 1;
                }
            }
            return maxlen;
        }
    };

  • 0
    V

    What's your run time?
    My solution 52 ms


  • 0
    Z

    Sadly my runtime is 128ms


Log in to reply
 

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