真实面经题目 · 原创解析
螺旋数组填充:给一个数组,返回一个 m*n 的矩阵,数从小到大顺时针螺旋填充矩阵,要求 |m-n| 尽可能小
这题考察矩阵尺寸选择和边界模拟。先根据数组长度找最接近的 m、n,再用四个边界按顺时针方向填充,重点处理单行单列和越界收缩。
真实面经题目 · 原创解析
这题考察矩阵尺寸选择和边界模拟。先根据数组长度找最接近的 m、n,再用四个边界按顺时针方向填充,重点处理单行单列和越界收缩。
我会先对数组排序,令 len 为长度,从 floor(sqrt(len)) 向下找第一个能整除 len 的因子作为较小维度 m,另一个维度 n=len/m,这样 |m-n| 最小。然后创建 m*n 矩阵,维护 top、bottom、left、right 四个边界,按从左到右、从上到下、从右到左、从下到上的顺序填入元素,每走完一条边就收缩对应边界。每轮都要判断 top<=bottom、left<=right,避免最后只剩一行或一列时重复填充。时间复杂度主要是排序 O(klogk) 加填充 O(k),空间 O(k)。
题目要求 |m-n| 尽可能小,所以不能随便取 1*len。最接近的因子一定在 sqrt(len) 附近,从 floor(sqrt(len)) 向下找第一个能整除 len 的数即可得到较小维度。
题干要求数从小到大顺时针填充,如果输入数组未保证有序,需要先升序排序。若面试官明确输入已排序,可以省略排序并说明复杂度相应降低。
用 top、bottom、left、right 表示当前还没填的矩形边界。依次填上边、右边、下边、左边,每填完一条边就向内收缩一格,直到元素全部填完。
当只剩一行时,填完上边后 top 已经大于 bottom,不应该再填下边。当只剩一列时,填完右边后 left 已经大于 right,不应该再填左边。每段循环前都要检查边界。
填充部分每个元素只写一次,是 O(k)。矩阵本身占 O(k) 空间。实现时用 idx 指向已消费的排序数组,比每次 shift 更高效,因为 shift 会移动数组元素。
function spiralFill(nums) {
const values = [...nums].sort((a, b) => a - b);
const len = values.length;
if (len === 0) return [];
let rows = Math.floor(Math.sqrt(len));
while (len % rows !== 0) rows--;
const cols = len / rows;
const matrix = Array.from({ length: rows }, () => Array(cols));
let top = 0;
let bottom = rows - 1;
let left = 0;
let right = cols - 1;
let i = 0;
while (top <= bottom && left <= right) {
for (let c = left; c <= right; c++) matrix[top][c] = values[i++];
top++;
for (let r = top; r <= bottom; r++) matrix[r][right] = values[i++];
right--;
if (top <= bottom) {
for (let c = right; c >= left; c--) matrix[bottom][c] = values[i++];
bottom--;
}
if (left <= right) {
for (let r = bottom; r >= top; r--) matrix[r][left] = values[i++];
left++;
}
}
return matrix;
} 两个因子越接近,差值越小。较小因子不可能大于 sqrt(len),所以从 sqrt(len) 往下找到的第一个因子就是最接近的较小维度。
不用。可以说明如果题目保证升序,直接填充即可,复杂度从 O(klogk) 降到 O(k)。如果不保证,就必须先排序来满足题意。
只剩一行或一列时,四个方向并不都存在。如果不在填下边和左边前检查边界,可能重复覆盖同一行或同一列。
题目只要求 |m-n| 最小,通常让 rows 为较小因子、cols 为较大因子即可。如果面试官要求特定方向或行列关系,就按约定调整。