C++ two methods: union find and using map


  • 1
    X
    class Solution {
    public:
        // using map
        /*
        int longestConsecutive(vector<int>& nums) {
            unordered_map<int, int>m;
            int ans = -1;
            for(int i : nums){
                if(m.find(i) == m.end()){
                    int leftnum = (m.find(i - 1) != m.end() ? m[i - 1] : 0);
                    int rightnum = (m.find(i + 1) != m.end() ? m[i + 1] : 0);
                    m[i] = leftnum + rightnum + 1;
                    m[i - leftnum] = m[i];
                    m[i + rightnum] = m[i];
                    ans = max(ans, m[i]);
                }
            }
            return ans;
        }
        */
        //using union find
        vector<int> size;
        vector<int> p;
        int ans;
        int find(int x){
            return x == p[x] ? x : p[x] = find(p[x]);
        }
        void unionFind(int a, int b){
            int pa = find(a);
            int pb = find(b);
            if(pa == pb){
                return;
            }
            p[pa] = pb;
            size[pb] += size[pa];
            ans = max(ans, size[pb]);
        }
        int longestConsecutive(vector<int>& nums) {
            if(nums.size() == 0){
                return 0;
            }
            ans = 1;
            p = vector<int>(nums.size());
            size = vector<int>(nums.size(), 1);
            iota(p.begin(), p.end(), 0);
            unordered_map<int, int>m;
            int idx = -1;
            for(int i : nums){
                ++idx;
                if(m.find(i) == m.end()){
                    m[i] = idx;
                    if(m.find(i - 1) != m.end()){
                        unionFind(idx, m[i - 1]);
                    }
                    if(m.find(i + 1) != m.end()){
                        unionFind(idx, m[i + 1]);
                    }
                }
            }
            return ans;
        }
    };

  • 0
    P

    I feel using map is O(nlogn), cause when u insert elements into a map, it is like inserting a number into a sorted array


  • 0
    X

    oh, the unordered_map is a kind of hash map in c++ which is average O(1) , and map is red-black tree which is average O(logN).


  • 0
    D
    This post is deleted!

  • 0
    D

    Union n find operation take logn time which will result in O(nlogn) complexity...


  • 0
    X

    No, union find is not logn. it's nearly linear.
    it's O(M* Alpha(N))
    where M is the num of search, N is the num of union,
    so the average is O(1).


Log in to reply
 

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