Hard
题目描述
给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示笛卡尔平面上第 i 个点的坐标。
两点 points[i] = [xi, yi] 和 points[j] = [xj, yj] 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。
将 n 个点分割成恰好两个非空组。分割的分割因子是同一组内所有无序点对之间曼哈顿距离的最小值。
返回所有有效分割中可能的最大分割因子。
注意： 大小为 1 的组不贡献组内点对。当 n = 2（两个组都大小为 1）时，没有组内点对，所以定义分割因子为 0。
示例 1：
输入：points = [[0,0],[0,2],[2,0],[2,2]]
输出：4
解释：
我们将点分成两组：{[0, 0], [2, 2]} 和 {[0, 2], [2, 0]}。
- 第一组中，唯一的点对曼哈顿距离为 |0 - 2| + |0 - 2| = 4。
- 第二组中，唯一的点对曼哈顿距离为 |0 - 2| + |2 - 0| = 4。
这个分割的分割因子是 min(4, 4) = 4，这是最大的。
示例 2：
输入：points = [[0,0],[0,1],[10,0]]
输出：11
解释：
我们将点分成两组：{[0, 1], [10, 0]} 和 {[0, 0]}。
- 第一组中，唯一的点对曼哈顿距离为 |0 - 10| + |1 - 0| = 11。
- 第二组是单例，不贡献点对。
这个分割的分割因子是 11，这是最大的。
约束条件：
2 <= points.length <= 500points[i] = [xi, yi]-10^8 <= xi, yi <= 10^8
解题思路
这道题的核心思想是使用二分搜索来找到最大的分割因子。
问题转化： 对于一个候选的分割因子 D，我们需要判断是否能够将所有点分成两组，使得每组内的最小曼哈顿距离都不小于 D。
关键洞察： 如果两个点的曼哈顿距离小于 D，那么它们必须被分到不同的组中。这样我们可以构建一个图：
- 顶点：所有的点
- 边：连接曼哈顿距离小于 D 的点对
二分图判断： 如果构建的图是二分图，说明可以将点分成两组满足条件；否则不可以。
算法步骤：
- 计算所有点对之间的曼哈顿距离
- 对所有距离进行排序，作为二分搜索的候选值
- 对每个候选值 D，构建约束图并检查是否为二分图
- 使用二分搜索找到最大的有效分割因子
时间复杂度： O(n² log n)，其中 n 是点的数量。二分搜索需要 O(log n²) 次迭代，每次需要 O(n²) 时间构建图和检查二分图。
代码实现
class Solution {
public:
int maxPartitionFactor(vector<vector<int>>& points) {
int n = points.size();
// 计算所有点对的曼哈顿距离
vector<int> distances;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
distances.push_back(dist);
}
}
sort(distances.begin(), distances.end());
distances.erase(unique(distances.begin(), distances.end()), distances.end());
int left = 0, right = distances.size() - 1;
int result = 0;
while (left <= right) {
int mid = (left + right) / 2;
int D = distances[mid];
if (isBipartite(points, D)) {
result = D;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
private:
bool isBipartite(vector<vector<int>>& points, int D) {
int n = points.size();
vector<vector<int>> graph(n);
// 构建图：距离小于D的点之间有边
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
if (dist < D) {
graph[i].push_back(j);
graph[j].push_back(i);
}
}
}
vector<int> color(n, -1);
// 检查是否为二分图
for (int i = 0; i < n; i++) {
if (color[i] == -1) {
if (!dfs(graph, i, 0, color)) {
return false;
}
}
}
return true;
}
bool dfs(vector<vector<int>>& graph, int node, int c, vector<int>& color) {
color[node] = c;
for (int neighbor : graph[node]) {
if (color[neighbor] == c || (color[neighbor] == -1 && !dfs(graph, neighbor, 1 - c, color))) {
return false;
}
}
return true;
}
};
class Solution:
def maxPartitionFactor(self, points: List[List[int]]) -> int:
n = len(points)
# 计算所有点对的曼哈顿距离
distances = []
for i in range(n):
for j in range(i + 1, n):
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
distances.append(dist)
distances = sorted(set(distances))
def is_bipartite(D):
# 构建图：距离小于D的点之间有边
graph = [[] for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
if dist < D:
graph[i].append(j)
graph[j].append(i)
color = [-1] * n
def dfs(node, c):
color[node] = c
for neighbor in graph[node]:
if color[neighbor] == c or (color[neighbor] == -1 and not dfs(neighbor, 1 - c)):
return False
return True
# 检查是否为二分图
for i in range(n):
if color[i] == -1:
if not dfs(i, 0):
return False
return True
left, right = 0, len(distances) - 1
result = 0
while left <= right:
mid = (left + right) // 2
D = distances[mid]
if is_bipartite(D):
result = D
left = mid + 1
else:
right = mid - 1
return result
public class Solution {
public int MaxPartitionFactor(int[][] points) {
int n = points.Length;
// 计算所有点对的曼哈顿距离
var distances = new HashSet<int>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dist = Math.Abs(points[i][0] - points[j][0]) + Math.Abs(points[i][1] - points[j][1]);
distances.Add(dist);
}
}
var sortedDistances = distances.OrderBy(x => x).ToArray();
int left = 0, right = sortedDistances.Length - 1;
int result = 0;
while (left <= right) {
int mid = (left + right) / 2;
int D = sortedDistances[mid];
if (IsBipartite(points, D)) {
result = D;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
private bool IsBipartite(int[][] points, int D) {
int n = points.Length;
var graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
// 构建图：距离小于D的点之间有边
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dist = Math.Abs(points[i][0] - points[j][0]) + Math.Abs(points[i][1] - points[j][1]);
if (dist < D) {
graph[i].Add(j);
graph[j].Add(i);
}
}
}
var color = new int[n];
Array.Fill(color, -1);
// 检查是否为二分图
for (int i = 0; i < n; i++) {
if (color[i] == -1) {
if (!Dfs(graph, i, 0, color)) {
return false;
}
}
}
return true;
}
private bool Dfs(List<int>[] graph, int node, int c, int[] color) {
color[node] = c;
foreach (int neighbor in graph[node]) {
if (color[neighbor] == c || (color[neighbor] == -1 && !Dfs(graph, neighbor, 1 - c, color))) {
return false;
}
}
return true;
}
}
var maxPartitionFactor = function(points) {
const n = points.length;
if (n === 2) return 0;
const manhattanDistance = (p1, p2) => Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
const getMinDistance = (group) => {
if (group.length <= 1) return Infinity;
let min = Infinity;
for (let i = 0; i < group.length; i++) {
for (let j = i + 1; j < group.length; j++) {
min = Math.min(min, manhattanDistance(group[i], group[j]));
}
}
return min;
};
let maxFactor = 0;
for (let mask = 1; mask < (1 << n) - 1; mask++) {
const group1 = [];
const group2 = [];
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) {
group1.push(points[i]);
} else {
group2.push(points[i]);
}
}
const min1 = getMinDistance(group1);
const min2 = getMinDistance(group2);
const partitionFactor = Math.min(min1, min2);
maxFactor = Math.max(maxFactor, partitionFactor);
}
return maxFactor;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n² log n) | 其中n是点的数量。计算距离需要O(n²)，二分搜索需要O(log n)次迭代，每次检查二分图需要O(n²) |
| 空间复杂度 | O(n²) | 存储图的邻接表和颜色数组 |