problem:https://leetcode.com/problems/longest-consecutive-sequence/
使用并查集,时间不是严格的O(n)
class Solution { public: unordered_map<int, int> p; int Find(int x) { while (x != p[x]) { x = p[x]; } return x; } void Union(int x, int y) { int px = Find(x); int py = Find(y); if (px != py) { p[px] = py; } } int longestConsecutive(vector<int>& nums) { unordered_set<int> s; for (int i = 0; i < nums.size(); i++) { p[nums[i]] = nums[i]; } for (int i = 0; i < nums.size(); i++) { if (nums[i] != INT_MAX && s.find(nums[i] + 1) != s.end()) { Union(nums[i], nums[i] + 1); } if (nums[i] != INT_MIN && s.find(nums[i] - 1) != s.end()) { Union(nums[i], nums[i] - 1); } s.insert(nums[i]); } int res = 0; unordered_map<int, int> count; for (auto& n : p) { int parent = Find(n.first); //cout << n.first << " " << parent << endl; count[parent]++; res = max(res, count[parent]); } return res; } };