真实面经题目 · 原创解析

螺旋数组填充:给一个数组,返回一个 m*n 的矩阵,数从小到大顺时针螺旋填充矩阵,要求 |m-n| 尽可能小

这题考察矩阵尺寸选择和边界模拟。先根据数组长度找最接近的 m、n,再用四个边界按顺时针方向填充,重点处理单行单列和越界收缩。

出现于:蚂蚁集团 · 前端

60 秒回答模板

我会先对数组排序,令 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)。

考点 核心机制与工程取舍
难度 中高频面试题
回答目标 按定义、机制、场景讲清楚

深入解析

01

先确定矩阵尺寸

题目要求 |m-n| 尽可能小,所以不能随便取 1*len。最接近的因子一定在 sqrt(len) 附近,从 floor(sqrt(len)) 向下找第一个能整除 len 的数即可得到较小维度。

02

再明确排序口径

题干要求数从小到大顺时针填充,如果输入数组未保证有序,需要先升序排序。若面试官明确输入已排序,可以省略排序并说明复杂度相应降低。

03

四边界模拟

用 top、bottom、left、right 表示当前还没填的矩形边界。依次填上边、右边、下边、左边,每填完一条边就向内收缩一格,直到元素全部填完。

04

处理最后一圈

当只剩一行时,填完上边后 top 已经大于 bottom,不应该再填下边。当只剩一列时,填完右边后 left 已经大于 right,不应该再填左边。每段循环前都要检查边界。

05

复杂度和稳定实现

填充部分每个元素只写一次,是 O(k)。矩阵本身占 O(k) 空间。实现时用 idx 指向已消费的排序数组,比每次 shift 更高效,因为 shift 会移动数组元素。

javascript

螺旋填充矩阵

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) 的因子,直接把矩阵定成 1 行或任意 m、n。
  • 忘记输入可能无序,导致填充结果不是从小到大。
  • 最后一圈没有检查 top、bottom、left、right,单行单列时重复写入。
  • 用 shift 不断取数组头,隐藏增加 O(k²) 的移动成本。

面试官追问

为什么从 sqrt(len) 往下找因子?

两个因子越接近,差值越小。较小因子不可能大于 sqrt(len),所以从 sqrt(len) 往下找到的第一个因子就是最接近的较小维度。

如果输入数组已经有序还要排序吗?

不用。可以说明如果题目保证升序,直接填充即可,复杂度从 O(klogk) 降到 O(k)。如果不保证,就必须先排序来满足题意。

最后一圈为什么容易出错?

只剩一行或一列时,四个方向并不都存在。如果不在填下边和左边前检查边界,可能重复覆盖同一行或同一列。

m 和 n 谁作为行数更合适?

题目只要求 |m-n| 最小,通常让 rows 为较小因子、cols 为较大因子即可。如果面试官要求特定方向或行列关系,就按约定调整。