2624. 蜗牛排序

🟠   🔗 力扣 LeetCode

题目

Write code that enhances all arrays such that you can call the snail(rowsCount, colsCount) method that transforms the 1D array into a 2D array organised in the pattern known as snail traversal order. Invalid input values should output an empty array. If rowsCount * colsCount !== nums.length, the input is considered invalid.

Snail traversal order starts at the top left cell with the first value of the current array. It then moves through the entire first column from top to bottom, followed by moving to the next column on the right and traversing it from bottom to top. This pattern continues, alternating the direction of traversal with each column, until the entire current array is covered. For example, when given the input array [19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15] with rowsCount = 5 and colsCount = 4, the desired output matrix is shown below. Note that iterating the matrix following the arrows corresponds to the order of numbers in the original array.


Example 1:

Input:

nums = [19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15]

rowsCount = 5

colsCount = 4

Output:

[

[19,17,16,15],

[10,1,14,4],

[3,2,12,20],

[7,5,18,11],

[9,8,6,13]

]

Example 2:

Input:

nums = [1,2,3,4]

rowsCount = 1

colsCount = 4

Output: [[1, 2, 3, 4]]

Example 3:

Input:

nums = [1,3]

rowsCount = 2

colsCount = 2

Output: []

Explanation: 2 multiplied by 2 is 4, and the original array [1,3] has a length of 2; therefore, the input is invalid.

Constraints:

• 0 <= nums.length <= 250
• 1 <= nums[i] <= 1000
• 1 <= rowsCount <= 250
• 1 <= colsCount <= 250

题目大意

请你编写一段代码为所有数组实现 snail(rowsCount，colsCount) 方法，该方法将 1D 数组转换为以蜗牛排序的模式的 2D 数组。无效的输入值应该输出一个空数组。当 rowsCount * colsCount !==``nums.length 时。这个输入被认为是无效的。

蜗牛排序从左上角的单元格开始，从当前数组的第一个值开始。然后，它从上到下遍历第一列，接着移动到右边的下一列，并从下到上遍历它。将这种模式持续下去，每列交替变换遍历方向，直到覆盖整个数组。例如，当给定输入数组 [19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15] ，当 rowsCount = 5 且 colsCount = 4 时，需要输出矩阵如下图所示。注意，矩阵沿箭头方向对应于原数组中数字的顺序


提示：

• 0 <= nums.length <= 250
• 1 <= nums[i] <= 1000
• 1 <= rowsCount <= 250
• 1 <= colsCount <= 250

解题思路

思路一

1. 输入验证：
   • 首先检查 rowsCount * colsCount 是否等于 nums.length，如果不相等，则返回空数组，因为此时无法将 nums 重组成指定行列数的二维数组。
2. 初始化二维数组：
   • 创建一个大小为 rowsCount x colsCount 的空二维数组 res，用于存储最终的结果。
3. 填充数组：
   • 使用一个索引 index，从 0 开始依次取出 nums 中的元素并填充到 res 中。
   • 遍历 col 列，对于每一列 col，需要判断当前列是自上而下填充还是自下而上填充。
     • 如果 col 是偶数列，则自上而下填充。
     • 如果 col 是奇数列，则自下而上填充。
4. 返回结果：
   • 当所有元素填充完毕后，返回 res，即按蜗牛遍历顺序填充的二维数组。

复杂度分析

• 时间复杂度：O(n)，其中 n = rowsCount * colsCount，由于遍历了 nums 数组的所有元素。
• 空间复杂度：O(n)，结果数组需要 n = rowsCount * colsCount 的存储空间。

思路二

填充数组的时候，还可以遍历 nums 中的元素，然后根据元素下标 i 来动态计算行和列：

1. 计算当前元素所在的列数：col = (i / rowsCount) | 0；
2. 先计算当前元素所在列的奇偶：dirction = col % 2 == 0；
3. 计算当前元素所在的行数：
   • 若列数是奇数（dirction == true），从上往下填充，行数为：row = i % rowsCount；
   • 若列数是偶数（dirction == false），从下往上填充，行数为：row = rowsCount - 1 - (i % rowsCount)；
4. 将 nums[i] 填充到 res[row][col]；

复杂度分析

• 时间复杂度：O(n)，其中 n = rowsCount * colsCount，由于遍历了 nums 数组的所有元素。
• 空间复杂度：O(n)，结果数组需要 n = rowsCount * colsCount 的存储空间。

代码

思路一

/**
 * @param {number} rowsCount
 * @param {number} colsCount
 * @return {Array<Array<number>>}
 */
Array.prototype.snail = function (rowsCount, colsCount) {
	if (rowsCount * colsCount !== this.length) return [];

	let res = new Array(rowsCount).fill(0).map((i) => new Array(colsCount));
	let index = 0;

	for (let col = 0; col < colsCount; col++) {
		if (col % 2 === 0) {
			// 从上到下填充这一列
			for (let row = 0; row < rowsCount; row++) {
				res[row][col] = this[index++];
			}
		} else {
			// 从下到上填充这一列
			for (let row = rowsCount - 1; row >= 0; row--) {
				res[row][col] = this[index++];
			}
		}
	}

	return res;
};

/**
 * const arr = [1,2,3,4];
 * arr.snail(1,4); // [[1,2,3,4]]
 */

思路二

/**
 * @param {number} rowsCount
 * @param {number} colsCount
 * @return {Array<Array<number>>}
 */
Array.prototype.snail = function (rowsCount, colsCount) {
	if (rowsCount * colsCount !== this.length) return [];
	let res = new Array(rowsCount).fill(0).map((i) => new Array(colsCount));
	for (let i = 0; i < rowsCount * colsCount; i++) {
		const col = (i / rowsCount) | 0;
		const dirction = col % 2 == 0;
		const row = dirction ? i % rowsCount : rowsCount - 1 - (i % rowsCount);
		res[row][col] = this[i];
	}
	return res;
};

/**
 * const arr = [1,2,3,4];
 * arr.snail(1,4); // [[1,2,3,4]]
 */

相关题目

题号	标题	题解	标签	难度
2619	数组原型对象的最后一个元素	[✓]
2631	分组	[✓]
2774	数组的上界 🔒