Hard
题目描述
给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点的坐标。points 中的所有坐标都是不同的。
如果一个点被激活，那么所有与它具有相同 x 坐标或相同 y 坐标的点也会被激活。
激活会持续进行，直到没有更多的点可以被激活。
你可以在任意一个不在 points 中的整数坐标 (x, y) 处添加一个额外的点。激活过程从激活这个新添加的点开始。
返回一个整数，表示可以激活的点的最大数量，包括新添加的点。
示例 1：
输入：points = [[1,1],[1,2],[2,2]]
输出：4
解释：
添加并激活点 (1, 3) 会导致激活：
- (1, 3) 与 (1, 1) 和 (1, 2) 共享 x = 1 -> (1, 1) 和 (1, 2) 被激活。
- (1, 2) 与 (2, 2) 共享 y = 2 -> (2, 2) 被激活。
因此，激活的点是 (1, 3), (1, 1), (1, 2), (2, 2)，总共 4 个点。
示例 2：
输入：points = [[2,2],[1,1],[3,3]]
输出：3
解释：
添加并激活点 (1, 2) 会导致激活：
- (1, 2) 与 (1, 1) 共享 x = 1 -> (1, 1) 被激活。
- (1, 2) 与 (2, 2) 共享 y = 2 -> (2, 2) 被激活。
因此，激活的点是 (1, 2), (1, 1), (2, 2)，总共 3 个点。
示例 3：
输入：points = [[2,3],[2,2],[1,1],[4,5]]
输出：4
解释：
添加并激活点 (2, 1) 会导致激活：
- (2, 1) 与 (2, 3) 和 (2, 2) 共享 x = 2 -> (2, 3) 和 (2, 2) 被激活。
- (2, 1) 与 (1, 1) 共享 y = 1 -> (1, 1) 被激活。
因此，激活的点是 (2, 1), (2, 3), (2, 2), (1, 1)，总共 4 个点。
提示：
1 <= points.length <= 10^5points[i] = [xi, yi]-10^9 <= xi, yi <= 10^9points包含所有不同的坐标。
解题思路
这是一个图连通性问题，可以使用并查集（Union-Find）来解决。
核心思路：
- 将所有具有相同 x 坐标或 y 坐标的点连接成一个连通分量
- 添加一个新点
(x0, y0)最多可以连接两个不同的连通分量：一个是包含 x 坐标为 x0 的点的分量，另一个是包含 y 坐标为 y0 的点的分量 - 如果这两个分量是同一个，那么激活的点数 = 该分量大小 + 1
- 如果这两个分量不同，那么激活的点数 = 分量A大小 + 分量B大小 + 1
算法步骤：
- 使用并查集将所有点按照相同的 x 或 y 坐标进行合并
- 为每个 x 坐标和 y 坐标分别建立映射，记录它们对应的连通分量
- 枚举所有可能的 x 坐标和 y 坐标组合，计算连接后的最大激活点数
- 特殊情况：如果所有点已经在一个连通分量中，答案是 n + 1
推荐解法： 使用并查集 + 哈希表的组合方法，时间复杂度最优。
代码实现
class Solution {
private:
vector<int> parent, size;
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
}
}
public:
int maxActivated(vector<vector<int>>& points) {
int n = points.size();
parent.resize(n);
size.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
unordered_map<int, vector<int>> xGroups, yGroups;
for (int i = 0; i < n; i++) {
int x = points[i][0], y = points[i][1];
xGroups[x].push_back(i);
yGroups[y].push_back(i);
}
for (auto& [x, indices] : xGroups) {
for (int i = 1; i < indices.size(); i++) {
unite(indices[0], indices[i]);
}
}
for (auto& [y, indices] : yGroups) {
for (int i = 1; i < indices.size(); i++) {
unite(indices[0], indices[i]);
}
}
unordered_map<int, int> xToComp, yToComp;
for (int i = 0; i < n; i++) {
int x = points[i][0], y = points[i][1];
int comp = find(i);
xToComp[x] = comp;
yToComp[y] = comp;
}
int maxActivated = 0;
for (auto& [x, compX] : xToComp) {
for (auto& [y, compY] : yToComp) {
if (compX == compY) {
maxActivated = max(maxActivated, size[compX] + 1);
} else {
maxActivated = max(maxActivated, size[compX] + size[compY] + 1);
}
}
}
return maxActivated;
}
};
class Solution:
def maxActivated(self, points: list[list[int]]) -> int:
n = len(points)
parent = list(range(n))
size = [1] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def unite(x, y):
x, y = find(x), find(y)
if x != y:
if size[x] < size[y]:
x, y = y, x
parent[y] = x
size[x] += size[y]
from collections import defaultdict
x_groups = defaultdict(list)
y_groups = defaultdict(list)
for i, (x, y) in enumerate(points):
x_groups[x].append(i)
y_groups[y].append(i)
for indices in x_groups.values():
for i in range(1, len(indices)):
unite(indices[0], indices[i])
for indices in y_groups.values():
for i in range(1, len(indices)):
unite(indices[0], indices[i])
x_to_comp = {}
y_to_comp = {}
for i, (x, y) in enumerate(points):
comp = find(i)
x_to_comp[x] = comp
y_to_comp[y] = comp
max_activated = 0
for comp_x in x_to_comp.values():
for comp_y in y_to_comp.values():
if comp_x == comp_y:
max_activated = max(max_activated, size[comp_x] + 1)
else:
max_activated = max(max_activated, size[comp_x] + size[comp_y] + 1)
return max_activated
public class Solution {
private int[] parent, size;
private int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
private void Unite(int x, int y) {
x = Find(x);
y = Find(y);
if (x != y) {
if (size[x] < size[y]) {
int temp = x;
x = y;
y = temp;
}
parent[y] = x;
size[x] += size[y];
}
}
public int MaxActivated(int[][] points) {
int n = points.Length;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
var xGroups = new Dictionary<int, List<int>>();
var yGroups = new Dictionary<int, List<int>>();
for (int i = 0; i < n; i++) {
int x = points[i][0], y = points[i][1];
if (!xGroups.ContainsKey(x)) xGroups[x] = new List<int>();
if (!yGroups.ContainsKey(y)) yGroups[y] = new List<int>();
xGroups[x].Add(i);
yGroups[y].Add(i);
}
foreach (var indices in xGroups.Values) {
for (int i = 1; i < indices.Count; i++) {
Unite(indices[0], indices[i]);
}
}
foreach (var indices in yGroups.Values) {
for (int i = 1; i < indices.Count; i++) {
Unite(indices[0], indices[i]);
}
}
var xToComp = new Dictionary<int, int>();
var yToComp = new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
int x = points[i][0], y = points[i][1];
int comp = Find(i);
xToComp[x] = comp;
yToComp[y] = comp;
}
int maxActivated = 0;
foreach (var compX in xToComp.Values) {
foreach (var compY in yToComp.Values) {
if (compX == compY) {
maxActivated = Math.Max(maxActivated, size[compX] + 1);
} else {
maxActivated = Math.Max(maxActivated, size[compX] + size[compY] + 1);
}
}
}
return maxActivated;
}
}
var maxActivated = function(points) {
const n = points.length;
const xMap = new Map();
const yMap = new Map();
// Group points by x and y coordinates
for (let i = 0; i < n; i++) {
const [x, y] = points[i];
if (!xMap.has(x)) xMap.set(x, []);
if (!yMap.has(y)) yMap.set(y, []);
xMap.get(x).push(i);
yMap.get(y).push(i);
}
// Build adjacency list for connected components
const adj = Array(n).fill().map(() => []);
for (const indices of xMap.values()) {
for (let i = 0; i < indices.length; i++) {
for (let j = i + 1; j < indices.length; j++) {
adj[indices[i]].push(indices[j]);
adj[indices[j]].push(indices[i]);
}
}
}
for (const indices of yMap.values()) {
for (let i = 0; i < indices.length; i++) {
for (let j = i + 1; j < indices.length; j++) {
adj[indices[i]].push(indices[j]);
adj[indices[j]].push(indices[i]);
}
}
}
// Find connected components
const visited = new Array(n).fill(false);
const components = [];
for (let i = 0; i < n; i++) {
if (!visited[i]) {
const component = [];
const stack = [i];
while (stack.length > 0) {
const node = stack.pop();
if (!visited[node]) {
visited[node] = true;
component.push(node);
for (const neighbor of adj[node]) {
if (!visited[neighbor]) {
stack.push(neighbor);
}
}
}
}
components.push(component);
}
}
let maxPoints = 0;
// Try adding a point that connects components
for (let i = 0; i < components.length; i++) {
for (let j = i; j < components.length; j++) {
const comp1 = components[i];
const comp2 = components[j];
const xs1 = new Set(comp1.map(idx => points[idx][0]));
const ys1 = new Set(comp1.map(idx => points[idx][1]));
const xs2 = new Set(comp2.map(idx => points[idx][0]));
const ys2 = new Set(comp2.map(idx => points[idx][1]));
let connected = new Set();
connected = new Set([...comp1, ...comp2]);
// Try to connect more components through shared x or y coordinates
const allXs = new Set([...xs1, ...xs2]);
const allYs = new Set([...ys1, ...ys2]);
for (let k = 0; k < components.length; k++) {
if (k === i || k === j) continue;
const comp = components[k];
const compXs = new Set(comp.map(idx => points[idx][0]));
const compYs = new Set(comp.map(idx => points[idx][1]));
let canConnect = false;
for (const x of compXs) {
if (allXs.has(x)) {
canConnect = true;
break;
}
}
if (!canConnect) {
for (const y of compYs) {
if (allYs.has(y)) {
canConnect = true;
break;
}
}
}
if (canConnect) {
for (const idx of comp) {
connected.add(idx);
}
for (const x of compXs) allXs.add(x);
for (const y of compYs) allYs.add(y);
k = -1; // Restart to check if we can connect more
}
}
maxPoints = Math.max(maxPoints, connected.size + 1);
}
}
return maxPoints;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n × α(n) + X × Y) | 其中 n 是点的数量，α 是阿克曼函数的反函数，X 和 Y 分别是不同 x 坐标和 y 坐标的数量，在最坏情况下 X×Y = O(n²) |
| 空间复杂度 | O(n) | 并查集数组和哈希 |