C++ Union-Find amotrized O(n)


  • 9
    S
    class Solution {
        vector<int> id;
        vector<int> size;
    public:
        int longestConsecutive(vector<int>& nums) {
            int n = nums.size();
            if(n < 2) return n;
            size = vector<int>(n,1);
            for(int i = 0; i < n; i++) {
                id.push_back(i);
            }
            unordered_map<int,int> record;
            for(int i = 0 ; i < n; i++) {
                if(record.find(nums[i]) != record.end()) continue;
                record[nums[i]] = i;
                if(record.find(nums[i]-1) != record.end()) {
                    unionSet(i,record[nums[i]-1]);
                }
                if(record.find(nums[i]+1) != record.end()) {
                    unionSet(i,record[nums[i]+1]);
                }
            }
            int res = *max_element(size.begin(),size.end());
            return res;
        }
        
        int find(int p) {
            while(p != id[p]) {
                id[p] = id[id[p]];
                p = id[p];
            }
            return p;
        }
        void unionSet(int a, int b) {
            int i = find(a);
            int j = find(b);
            if(i == j) return;
            if(size[i] > size[j]) {
                id[j] = i;
                size[i] += size[j];
            } else {
                id[i] = j;
                size[j] += size[i];
            }
        }
    };

  • 1
    F

    For those who are interested in union-find, here is a tutorial from Princeton U:

    I have a similar solution in Java, runtime is 15 ms:

    public class Solution {
        
        private int n;
        private int ids[];
        private int sizes[];
        private int maxSize;
        
        public int longestConsecutive(int[] nums) {
            if ((n = nums.length) == 0) return 0;
            sizes = new int[n];
            ids = new int[n];
            Map<Integer, Integer> map = new HashMap<>();
            Arrays.fill(sizes, 1);
            maxSize = 1;
            for (int i = 0; i < n; i++) {
                if (map.containsKey(nums[i])) {
                    continue;
                }
                map.put(nums[i], i);
                ids[i] = i;
                if (map.containsKey(nums[i] - 1)) {
                    unite(i, map.get(nums[i] - 1));
                }
                if (map.containsKey(nums[i] + 1)) {
                    unite(i, map.get(nums[i] + 1));
                }
            }
            
            return maxSize;
        }
        
        private void unite(int a, int b) {
            int rootA = findRoot(a);
            int rootB = findRoot(b);
            if (rootA == rootB) {
                return;
            }
            int small;
            int large;
            if (sizes[rootA] > sizes[rootB]) {
                small = rootB;
                large = rootA;
            } else {
                small = rootA;
                large = rootB;
            }
            ids[small] = large;
            sizes[large] += sizes[small];
            if (sizes[large] > maxSize) {
                maxSize = sizes[large];
            }
        }
        
        private int findRoot(int i) {
            while (i != ids[i]) {
                ids[i] = ids[ids[i]];
                i = ids[i];
            }
            
            return i;
        }
    }
    

  • 0
    J

    Hi, I got accepted using similar idea

        unordered_map<int, int> m;  
        
        int findParent(int n){
            while(m[n] != n)
                n = m[n] = m[m[n]]; 
            return n;
        }    
        
        int longestConsecutive(vector<int>& nums) {
    	    int r = 0;
    	    for (int &i : nums) {
    		if (m[i]) continue;
    		m[i] = i;
                    if (m.find(i-1) != m.end())
                        m[i] = findParent(i-1);
                    if (m.find(i+1) != m.end())
                        m[i+1] = m[i];
    	    }
    	    for (int &i : nums)
        	        r = max(r, i - findParent(i) + 1);    
        	    return r;   
        }
    

    At the first glance I was thinking this method should be O(nlogn), but it runs in 16ms, even better than my strict O(n) algo. Can anyone give me a rigious proof on its amortized complexity?


Log in to reply
 

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