DeepSeek LeetCode 3710. 最大划分因子 Java实现

这道题的核心解法是 二分答案 二分图判定。· 核心思路要最大化“划分因子”可以将其转化为判定问题对于某个距离 d能否将所有点分成两组使得同一组内任意两点的曼哈顿距离都 ≥ d。Java 代码实现javaimport java.util.Arrays;class Solution {public int maxPartitionFactor(int[][] points) {int n points.length;if (n 2) return 0; // 两个点必须各分一组无组内点对// 1. 预处理所有点对之间的曼哈顿距离int[][] dist new int[n][n];int maxDist 0;for (int i 0; i n; i) {for (int j i 1; j n; j) {int d Math.abs(points[i][0] - points[j][0]) Math.abs(points[i][1] - points[j][1]);dist[i][j] dist[j][i] d;maxDist Math.max(maxDist, d);}}// 2. 二分查找最大可行的划分因子int low 0, high maxDist;while (low high) {// 取偏右的中位数避免死循环int mid low (high - low 1) / 2;if (isFeasible(dist, mid)) {low mid; // mid可行尝试更大的值} else {high mid - 1; // mid不可行尝试更小的值}}return low;}// 判定是否存在一种分组使同一组内任意两点距离都 tprivate boolean isFeasible(int[][] dist, int t) {int n dist.length;int[] color new int[n];Arrays.fill(color, -1); // -1表示未染色// 对每个连通分量进行BFS/DFS染色for (int i 0; i n; i) {if (color[i] ! -1) continue;// BFS队列int[] queue new int[n];int head 0, tail 0;queue[tail] i;color[i] 0; // 染色为0while (head tail) {int u queue[head];for (int v 0; v n; v) {if (u v || dist[u][v] t) continue;// 距离 t 的点必须分到不同组即形成一条边[reference:2]if (color[v] -1) {color[v] color[u] ^ 1; // 染成相反颜色queue[tail] v;} else if (color[v] color[u]) {return false; // 矛盾不是二分图}}}}return true; // 所有连通分量都可二分}}复杂度分析· 时间复杂度O(N² log D)。N是点数≤500D是最大曼哈顿距离。二分查找执行O(log D)次每次判定需遍历所有点对O(N²)。· 空间复杂度O(N²)用于存储距离矩阵。