Good method to use map in c++


  • -2
    H

    I read some threads in discuss, found that most of you want to use map or unsorted_map to store the length information for each element in num. However you may miss an important feature about map:

    map is based on red-black tree, so the key value is sorted in map, which is the great difference between map and unsorted_map, so we can exactly use the sorted key value to calculate the longest length

    following is my code:

    class Solution {
    public:
        int longestConsecutive(vector<int> &num) {
            map<int, int> m;
            for(int i=0;i<num.size();i++){
                m[num[i]]++;
            }
            
            int ret=1;
            int cur_len=1;
            
            map<int, int>::iterator it;
            int last=m.begin()->first;
            
            for(it=m.begin();it!=m.end();it++){
                int cur=it->first;
                
                if(cur==last) continue;
                else if(cur==last+1){
                    cur_len++;
                    ret=max(ret,cur_len);
                    last=cur;
                }
                else{
                    cur_len=1;
                    last=cur;
                }
            }
            
            return ret;
        }
    };

  • 0
    G

    As you said, map is based on rb-tree, so the insert method of map is logn, then I think the code run time below is O(nlogn),not O(n), what do you say?
    for(int i=0;i<num.size();i++){
    m[num[i]]++;
    }


Log in to reply
 

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