We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
No description provided.
The text was updated successfully, but these errors were encountered:
并查集做法
/** * @param {number[]} nums * @return {number} */ class UnionSet { constructor(n) { this.fa = Array(n + 1) this.cut = Array(n + 1).fill(1) for (let i = 0; i < n; i++) { this.fa[i] = i } } get(x) { return this.fa[x] = (this.fa[x] == x ? x : this.get(this.fa[x])) } merge(a, b) { let sa = this.get(a), sb = this.get(b) if (sa == sb) return this.cut[sa] += this.cut[sb] this.fa[sb] = sa } } //核心点在于想到维护的集合是什么 //PS:找数组中是否有与x相邻数(+/-) 此处是记录其在数组中位置 var longestConsecutive = function(nums) { //u维护的是位置而不是值(值可能很大) 寻找+-1的元素是否在数组中 是则连通其位置 //map记录的是元素位置 >=0则表示存在 let len = nums.length let u = new UnionSet(nums.length), map = {}, ans = 0 for(let i = 0; i < len; i++) { //如果是重复的元素则跳过 if (map[nums[i]] >= 0) continue if (map[nums[i] - 1] >= 0) { u.merge(i, map[nums[i] - 1]) } if (map[nums[i] + 1] >= 0) { u.merge(i, map[nums[i] + 1]) } map[nums[i]] = i } for(let i = 0; i < len; i++) { if (u.get(i) == i && u.cut[i] > ans) ans = u.cut[i] } return ans };
Sorry, something went wrong.
No branches or pull requests
No description provided.
The text was updated successfully, but these errors were encountered: