英语网站都可以做哪些内容,中国建设银行总行网站,优化国内访问wordpress,网页设计证书含金量高吗原题链接#x1f517;#xff1a;螺旋矩阵 难度#xff1a;中等⭐️⭐️
题目
给你一个 m 行 n 列的矩阵 matrix #xff0c;请按照 顺时针螺旋顺序 #xff0c;返回矩阵中的所有元素。
示例 1#xff1a;
输入#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出螺旋矩阵 难度中等⭐️⭐️
题目
给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素。
示例 1
输入matrix [[1,2,3],[4,5,6],[7,8,9]] 输出[1,2,3,6,9,8,7,4,5]
示例 2
输入matrix [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出[1,2,3,4,8,12,11,10,9,5,6,7]
提示 m matrix.length n matrix[i].length 1 m, n 10 -100 matrix[i][j] 1
题解
四指针遍历法
题解 这个算法不需要修改原始矩阵。以下是实现这个算法的步骤 初始化四个边界top 表示矩阵的顶部边界bottom 表示底部边界left 表示左侧边界right 表示右侧边界。创建一个空列表 result 用于存储按螺旋顺序排列的元素。使用一个循环直到 top 大于 bottom 或 left 大于 right 从 left 到 right 遍历 top 行将这些元素添加到 result。增加 top 的值缩小顶部边界。从 top 到 bottom 遍历 right 列将这些元素添加到 result。减少 right 的值缩小右侧边界。如果 top 小于等于 bottom从 right 到 left 遍历 bottom 行将这些元素添加到 result。减少 bottom 的值缩小底部边界。如果 left 小于等于 right从 bottom 到 top 遍历 left 列将这些元素添加到 result。增加 left 的值缩小左侧边界。 返回 result 列表它包含了矩阵中所有元素的顺时针螺旋顺序。 复杂度时间复杂度O(m×n)因为每个单元格都被填充一次空间复杂度O(m×n)用于存储最终的矩阵。过程 螺旋矩阵是一种特殊的矩阵其元素按照螺旋的方式填充从外圈向内圈逐渐填充每个元素的值依次递增。 实现过程如下 首先函数检查输入矩阵是否为空或其子数组是否为空。如果是则直接返回一个空的一维数组。 定义四个变量top, bottom, left, right来分别表示矩阵的上边界、下边界、左边界和右边界。 使用一个while循环当top不大于bottom且left不大于right时循环继续。这确保了矩阵中至少还有一行或一列可以遍历。 在循环内部首先从left到right遍历矩阵的顶部行将这些元素添加到结果数组中然后top加1。 接着从top到bottom遍历矩阵的最右列将这些元素添加到结果数组中然后right减1。 确保在继续之前当前的遍历行与上一次的遍历行不同如果top小于等于bottom从right到left遍历矩阵的底部行然后bottom减1。 同样确保在继续之前当前的遍历列与上一次的遍历列不同如果left小于等于right从bottom到top遍历矩阵的最左列然后left加1。 函数最后返回包含矩阵所有元素的一维数组这些元素按照螺旋顺序排列。 main函数中创建了3x3、3x4的两个矩阵并调用spiralOrder函数来获取螺旋顺序的元素然后打印这些元素。 c demo
#include iostream
#include vectorstd::vectorint spiralOrder(const std::vectorstd::vectorint matrix) {if (matrix.empty() || matrix[0].empty()) return {};std::vectorint result;int top 0, bottom matrix.size() - 1;int left 0, right matrix[0].size() - 1;while (top bottom left right) {// Traverse from left to right.for (int i left; i right; i) {result.push_back(matrix[top][i]);}top;// Traverse downwards.for (int i top; i bottom; i) {result.push_back(matrix[i][right]);}--right;// Make sure we are now on a different row.if (top bottom) {for (int i right; i left; --i) {result.push_back(matrix[bottom][i]);}--bottom;}// Make sure we are now on a different column.if (left right) {for (int i bottom; i top; --i) {result.push_back(matrix[i][left]);}left;}}return result;
}int main() {std::vectorstd::vectorint matrix {{1, 2, 3},{4, 5, 6},{7, 8, 9}};std::vectorint spiral spiralOrder(matrix);for (int num : spiral) {std::cout num ;}std::cout std::endl;std::vectorstd::vectorint matrix2 {{1, 2, 3, 4 },{5, 6, 7, 8 },{9, 10, 11, 12}};std::vectorint spiral2 spiralOrder(matrix2);for (int num : spiral2) {std::cout num ;}std::cout std::endl;return 0;
}输出结果 1 2 3 6 9 8 7 4 5 1 2 3 4 8 12 11 10 9 5 6 7
