JS按指定行列分割二维数组为正交连通子块的高效实现
2026-8-26
二维数组按删除行列拆分正交连通块高效实现方案
需求说明
- 目标：将二维数组移除指定行、列后，把剩余单元格按正交连通块（无删除行列阻隔的上下左右相邻单元格集合）拆分为多个独立二维子数组，所有子数组存入新数组返回
- 原数组规则：第N行第M列的单元格存储格式为
"N M"的字符串，例：第2行第3列值为"2 3" - 示例：8行7列数组，删除行
[2,3,5]、删除列[2,6]，预期返回结果如下：
[ [["0, 0", "0, 1"], ["1, 0", "1, 1"]], [["0, 3", "0, 4", "0, 5"], ["1, 3", "1, 4", "1, 5"]], [["4, 0", "4, 1"]], [["4, 3", "4, 4", "4, 5"]], [["6, 0", "6, 1"], ["7, 0", "7, 1"]], [["6, 3", "6, 4", "6, 5"], ["7, 3", "7, 4", "7, 5"]] ]
连通块判定规则：两个单元格之间如果没有被删除的行/列隔断，且正交（上下左右）相邻，就属于同一个连通块，最终每个连通块保持原相对行列位置组成独立二维数组。
现有问题
当前编写的测试实现运行时会错误包含待排除的列，已知问题成因，但不希望通过引入高复杂度逻辑修复（会降低执行效率），需要兼顾正确性和执行效率的实现方案。
现有测试代码如下：
const SourceArray = [ ['R0·C0', 'R0·C1', 'R0·C2', 'R0·C3', 'R0·C4', 'R0·C5', 'R0·C6'], ['R1·C0', 'R1·C1', 'R1·C2', 'R1·C3', 'R1·C4', 'R1·C5', 'R1·C6'], ['R2·C0', 'R2·C1', 'R2·C2', 'R2·C3', 'R2·C4', 'R2·C5', 'R2·C6'], ['R3·C0', 'R3·C1', 'R3·C2', 'R3·C3', 'R3·C4', 'R3·C5', 'R3·C6'], ['R4·C0', 'R4·C1', 'R4·C2', 'R4·C3', 'R4·C4', 'R4·C5', 'R4·C6'], ['R5·C0', 'R5·C1', 'R5·C2', 'R5·C3', 'R5·C4', 'R5·C5', 'R5·C6'], ['R6·C0', 'R6·C1', 'R6·C2', 'R6·C3', 'R6·C4', 'R6·C5', 'R6·C6'], ['R7·C0', 'R7·C1', 'R7·C2', 'R7·C3', 'R7·C4', 'R7·C5', 'R7·C6'] ]; function split2DArray_test() { let arrObjs = { oldArr: { obj: SourceArray, bounds: { row: 8, col: 7, }, setBounds: function() { this.bounds.row = this.obj.length; this.bounds.col = this.obj[0].length; }, }, newArr: { collection: [], component: [], design: { rInit: 0, rEnd: 0, cInit: 0, cEnd: 0 } }, splits: { atRows: [2, 3, 5], atCols: [2, 5] } }; arrObjs.oldArr.setBounds(); let i = { lv1_R: 0, lv2_C: 0 , lv3_R: 0, lv4_C: 0, slicer: 0 }; let escape = false; /* 1. 遍历行（第一层循环） 2. 遇到待删除行则跳过，遇到保留行则遍历列（第二层循环） 3. 遇到保留列则记录起始坐标，继续遍历列 4. 遇到待删除列则记录列终点为当前列索引-1，回到行遍历（第三层循环），遇到待删除行则记录行终点为当前行索引-1 5. 记录切片边界：[起始行, 起始列, 结束行, 结束列] 6. 初始化结果子数组容器 7. 遍历切片边界内的所有行（第四层循环），调用数组slice方法截取对应列范围的行片段，推入子数组容器 8. 将子数组推入最终结果集合 9. 将第二层列遍历的指针设置为结束列+1 10. 理论上逻辑可运行，未完成测试 */ console.log(`待删除行：${arrObjs.splits.atRows.join(', ')}`); console.log(`待删除列：${arrObjs.splits.atCols.join(', ')}`); console.time('slicer'); for (i.lv1_R = 0; i.lv1_R < arrObjs.oldArr.bounds.row; i.lv1_R++) { if (arrObjs.splits.atRows.includes(i.lv1_R)) { continue; } else { // 定位到非删除行 for (i.lv2_C = 0; i.lv2_C < arrObjs.oldArr.bounds.col; i.lv2_C++) { if (arrObjs.splits.atCols.includes(i.lv2_C)) { continue; } else { arrObjs.newArr.design.rInit = i.lv1_R; arrObjs.newArr.design.cInit = i.lv2_C; console.log(`找到起始单元格'${arrObjs.oldArr.obj[i.lv1_R][i.lv2_C]}'`); for (i.lv3_R = arrObjs.newArr.design.rInit; i.lv3_R < arrObjs.oldArr.bounds.row; i.lv3_R++) { if (arrObjs.splits.atRows.includes(i.lv3_R)) { arrObjs.newArr.design.rEnd = i.lv3_R - 1; for (i.lv4_C = arrObjs.newArr.design.cInit; i.lv4_C < arrObjs.oldArr.bounds.col; i.lv4_C++) { if (arrObjs.splits.atCols.includes(i.lv4_C)) { arrObjs.newArr.design.cEnd = i.lv4_C - 1; for (i.slicer = arrObjs.newArr.design.rInit; i.slicer < arrObjs.newArr.design.rEnd + 1; i.slicer++) { arrObjs.newArr.component.push([arrObjs.oldArr.obj[i.slicer].slice(arrObjs.newArr.design.cInit, arrObjs.newArr.design.cEnd + 1)]); }; arrObjs.newArr.collection.push('Split'); // 日志用分隔标记 arrObjs.newArr.collection.push(arrObjs.newArr.component); arrObjs.newArr.component = []; i.lv2_C += 1 + arrObjs.newArr.design.cEnd - arrObjs.newArr.design.cInit; arrObjs.newArr.design.rInit = 0; arrObjs.newArr.design.rEnd = 0; arrObjs.newArr.design.cInit = 0; arrObjs.newArr.design.cEnd = 0; escape = true; break; }; }; }; if (escape) { escape = false; break; }; }; }; }; i.lv2_R += 1 + arrObjs.newArr.design.rEnd - arrObjs.newArr.design.rInit; }; }; console.timeEnd('slicer'); console.log(`二维数组拆分结果：\n\n${(arrObjs.newArr.collection.join('\n\n'))}`); // 输出日志 /* 思路记录： ===== 待完善的方案思路 ===== 1. 记录第一个有效切片的左上角起始单元格 2. 从列最小值到列最大值遍历列 3. 遇到待删除列时，将切片列终点设为当前列索引-1 4. 从起始行开始向下遍历行，遇到待删除行或数组边界时，将切片行终点设为当前行索引-1 5. 遍历切片行范围，用slice截取对应列范围的行片段，组成子数组 6. 将子数组推入最终结果集合 === 待验证的思路方向 === I. 迭代单元格搜索 基于边界和删除位置设置遍历续跑标记：比如列遍历到数组边界时标记列续跑为false，遇到删除列时标记列续跑为true。每次推入一个完整二维子块后，根据标记决定是横向移动到下一个同层子块（续跑标记为true），还是纵向移动到下一层子块（续跑标记为false）。如果行列续跑标记都为false，说明所有子块都已提取完成。 只要有一个续跑标记为true，就可以继续遍历，两个标记都为true时即可定位新的切片起始点。 II. 迭代边界与删除项搜索 1. 先确定数组整体边界，裁剪掉边界外的无效删除项（已完成） > 此时剩余的删除项位置就是目标切片的左上边界 2. 优先遍历列方向的删除索引（首次循环从数组左上角边界开始），再遍历行方向的删除索引。每次将切片起始点设为(删除行索引+1, 删除列索引+1)，切片终点设为对应方向下一个删除项的索引位置。 */ };
高效实现方案
核心优化逻辑是跳过逐单元格连通性判断，先预处理连续保留段再直接拼接结果，整体时间复杂度为O(R+C+总单元格数)，无多余遍历，执行效率拉满：
- 预处理阶段：将待删除行、列转为Set实现O(1)存在性查询，再分别扫描行、列，把连续未被删除的区间拆分为独立的行段、列段。比如示例中删除行
[2,3,5]，拆分后的保留行段为[0-1], [4-4], [6-7]；删除列[2,6]，拆分后的保留列段为[0-1], [3-5] - 结果生成阶段：每个行段和列段的交叉区域天然就是一个独立连通块——被删除行列隔开的段之间不可能连通，同一段内的单元格必然正交连通，直接做行段和列段的笛卡尔积，用原生
slice方法截取对应区间即可，完全不需要BFS/DFS或者多层指针跳转。
实现代码
function split2DArray(source, deleteRows, deleteCols) { const rowCount = source.length; if (rowCount === 0) return []; const colCount = source[0].length; // 转Set实现O(1)删除项查询 const delRowSet = new Set(deleteRows); const delColSet = new Set(deleteCols); // 提取所有连续保留行段 const rowSegments = []; let segStart = -1; for (let r = 0; r <= rowCount; r++) { if (r < rowCount && !delRowSet.has(r)) { if (segStart === -1) segStart = r; } else { if (segStart !== -1) { rowSegments.push([segStart, r - 1]); segStart = -1; } } } // 提取所有连续保留列段 const colSegments = []; segStart = -1; for (let c = 0; c <= colCount; c++) { if (c < colCount && !delColSet.has(c)) { if (segStart === -1) segStart = c; } else { if (segStart !== -1) { colSegments.push([segStart, c - 1]); segStart = -1; } } } // 行段列段交叉直接生成所有连通块 const result = []; for (const [rStart, rEnd] of rowSegments) { for (const [cStart, cEnd] of colSegments) { const block = []; for (let r = rStart; r <= rEnd; r++) { // slice第二个参数为不包含的终止索引，所以传入cEnd+1 block.push(source[r].slice(cStart, cEnd + 1)); } result.push(block); } } return result; } // 测试用例 const testResult = split2DArray(SourceArray, [2,3,5], [2,6]); console.log(JSON.stringify(testResult, null, 2));
该实现完全规避了原代码多层嵌套循环的指针跳转bug，所有遍历均为线性扫描，且核心截取逻辑调用引擎底层实现的原生slice方法，执行效率远高于手动逐单元格拼接。
内容的提问来源于stack exchange，提问作者Pryor
相关产品推荐
相关产品推荐
