力扣00059.螺旋矩阵 II

发表于 分类于 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 8 分钟
螺旋矩阵 II、数组、矩阵、模拟、中等

题目描述

给你一个正整数 n ，生成一个包含 1 到 $n^2$ 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

  • 1 <= n <= 20

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n, vector<int>(n, 0));
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int num = 1;
        while (num <= n * n) {
            for (int i = left; i <= right; ++i) {
                matrix[top][i] = num++;
            }
            ++top;
            for (int i = top; i <= bottom; ++i) {
                matrix[i][right] = num++;
            }
            --right;
            for (int i = right; i >= left; --i) {
                matrix[bottom][i] = num++;
            }
            --bottom;
            for (int i = bottom; i >= top; --i) {
                matrix[i][left] = num++;
            }
            ++left;
        }
        return matrix;
    }
};

结果

执行用时 : 2 ms, 击败 31.17% 使用 C++ 的用户

内存消耗 : 7.64 MB, 击败 7.68% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int num = 1;
        while (num <= n * n) {
            for (int i = left; i <= right; ++i) {
                matrix[top][i] = num++;
            }
            ++top;
            for (int i = top; i <= bottom; ++i) {
                matrix[i][right] = num++;
            }
            --right;
            for (int i = right; i >= left; --i) {
                matrix[bottom][i] = num++;
            }
            --bottom;
            for (int i = bottom; i >= top; --i) {
                matrix[i][left] = num++;
            }
            ++left;
        }
        return matrix;
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 40.53 MB, 击败 11.79% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        matrix = [[0] * n for _ in range(n)]
        top, bottom, left, right = 0, n - 1, 0, n - 1
        num = 1
        while num <= n * n:
            for i in range(left, right + 1):
                matrix[top][i] = num
                num += 1
            top += 1
            for i in range(top, bottom + 1):
                matrix[i][right] = num
                num += 1
            right -= 1
            for i in range(right, left - 1, -1):
                matrix[bottom][i] = num
                num += 1
            bottom -= 1
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1
        return matrix

结果

执行用时 : 12 ms, 击败 87.28% 使用 Python 的用户

内存消耗 : 11.32 MB, 击败 97.99% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0] * n for _ in range(n)]
        top, bottom, left, right = 0, n - 1, 0, n - 1
        num = 1
        while num <= n * n:
            for i in range(left, right + 1):
                matrix[top][i] = num
                num += 1
            top += 1
            for i in range(top, bottom + 1):
                matrix[i][right] = num
                num += 1
            right -= 1
            for i in range(right, left - 1, -1):
                matrix[bottom][i] = num
                num += 1
            bottom -= 1
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1
        return matrix

结果

执行用时 : 31 ms, 击败 93.71% 使用 Python3 的用户

内存消耗 : 16.50 MB, 击败 40.40% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
    int** matrix = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; ++i) {
        matrix[i] = (int*)malloc(n * sizeof(int));
    }
    int top = 0, bottom = n - 1, left = 0, right = n - 1;
    int num = 1;
    while (num <= n * n) {
        for (int i = left; i <= right; ++i) {
            matrix[top][i] = num++;
        }
        ++top;
        for (int i = top; i <= bottom; ++i) {
            matrix[i][right] = num++;
        }
        --right;
        for (int i = right; i >= left; --i) {
            matrix[bottom][i] = num++;
        }
        --bottom;
        for (int i = bottom; i >= top; --i) {
            matrix[i][left] = num++;
        }
        ++left;
    }
    *returnSize = n;
    *returnColumnSizes = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; ++i) {
        (*returnColumnSizes)[i] = n;
    }
    return matrix;
}

结果

执行用时 : 2 ms, 击败 62.52% 使用 C 的用户

内存消耗 : 6.06 MB, 击败 76.93% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int[][] GenerateMatrix(int n) {
        int[][] matrix = new int[n][];
        for (int i = 0; i < n; i++) {
            matrix[i] = new int[n];
        }
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int num = 1;
        while (num <= n * n) {
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;
            for (int i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--;
            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }
        return matrix;
    }
}

结果

执行用时 : 73 ms, 击败 68.89% 使用 C# 的用户

内存消耗 : 37.83 MB, 击败 33.34% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let matrix = new Array(n).fill().map(() => new Array(n).fill(0));
    let top = 0, bottom = n - 1, left = 0, right = n - 1;
    let num = 1;
    while (num <= n * n) {
        for (let i = left; i <= right; i++) {
            matrix[top][i] = num++;
        }
        top++;
        for (let i = top; i <= bottom; i++) {
            matrix[i][right] = num++;
        }
        right--;
        for (let i = right; i >= left; i--) {
            matrix[bottom][i] = num++;
        }
        bottom--;
        for (let i = bottom; i >= top; i--) {
            matrix[i][left] = num++;
        }
        left++;
    }
    return matrix;
};

结果

执行用时 : 57 ms, 击败 65.69% 使用 JavaScript 的用户

内存消耗 : 49.21 MB, 击败 16.31% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function generateMatrix(n: number): number[][] {
    const matrix: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    let top = 0, bottom = n - 1, left = 0, right = n - 1;
    let num = 1;
    while (num <= n * n) {
        for (let i = left; i <= right; i++) {
            matrix[top][i] = num++;
        }
        top++;
        for (let i = top; i <= bottom; i++) {
            matrix[i][right] = num++;
        }
        right--;
        for (let i = right; i >= left; i--) {
            matrix[bottom][i] = num++;
        }
        bottom--;
        for (let i = bottom; i >= top; i--) {
            matrix[i][left] = num++;
        }
        left++;
    }
    return matrix;
}

结果

执行用时 : 54 ms, 击败 95.24% 使用 TypeScript 的用户

内存消耗 : 51.67 MB, 击败 14.88% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {

    /**
     * @param Integer $n
     * @return Integer[][]
     */
    function generateMatrix($n) {
        $matrix = array_fill(0, $n, array_fill(0, $n, 0));
        $top = 0; $bottom = $n - 1; $left = 0; $right = $n - 1;
        $num = 1;
        while ($num <= $n * $n) {
            for ($i = $left; $i <= $right; $i++) {
                $matrix[$top][$i] = $num++;
            }
            $top++;
            for ($i = $top; $i <= $bottom; $i++) {
                $matrix[$i][$right] = $num++;
            }
            $right--;
            for ($i = $right; $i >= $left; $i--) {
                $matrix[$bottom][$i] = $num++;
            }
            $bottom--;
            for ($i = $bottom; $i >= $top; $i--) {
                $matrix[$i][$left] = $num++;
            }
            $left++;
        }
        return $matrix;
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 PHP 的用户

内存消耗 : 20.34 MB, 击败 12.50% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    func generateMatrix(_ n: Int) -> [[Int]] {
        var matrix = [[Int]].init(repeating: [Int].init(repeating: 0, count: n), count: n)
        var direction: Direction = .right
        var section = 0
        var row = 0
        for i in 1 ... (n * n) {
            if matrix[section][row] == 0 {
                matrix[section][row] = i
            }
            switch direction {
            case .right:
                if (row + 1) % n == 0 || matrix[section][row + 1] != 0 {
                    direction = .bottom
                    section += 1
                } else {
                    row += 1
                }
            case .bottom:
                if section == n - 1 || matrix[section + 1][row] != 0 {
                    direction = .left
                    row -= 1
                } else {
                    section += 1
                }
            case .left:
                if row == 0 || matrix[section][row - 1] != 0 {
                    direction = .top
                    section -= 1
                } else {
                    row -= 1
                }
            case .top:
                if section == 0 || matrix[section - 1][row] != 0 {
                    direction = .right
                    row += 1
                } else {
                    section -= 1
                }
            }
        }
        return matrix
    }
    enum Direction {
        case right, bottom, left, top
    }
}

结果

执行用时 : 6 ms, 击败 15.38% 使用 Swift 的用户

内存消耗 : 16.06 MB, 击败 5.13% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    fun generateMatrix(n: Int): Array<IntArray> {
        val matrix = Array(n) { IntArray(n) }
        var left = 0
        var right = n - 1
        var top = 0
        var bottom = n - 1
        var num = 1
        while (left <= right && top <= bottom) {
            for (i in left..right) {
                matrix[top][i] = num++
            }
            top++
            for (i in top..bottom) {
                matrix[i][right] = num++
            }
            right--
            if (top <= bottom) {
                for (i in right downTo left) {
                    matrix[bottom][i] = num++
                }
                bottom--
            }
            if (left <= right) {
                for (i in bottom downTo top) {
                    matrix[i][left] = num++
                }
                left++
            }
        }
        return matrix
    }
}

结果

执行用时 : 146 ms, 击败 60.00% 使用 Kotlin 的用户

内存消耗 : 33.64 MB, 击败 40.00% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  List<List<int>> generateMatrix(int n) {
    List<List<int>> matrix = List.generate(n, (index) => List<int>.filled(n, 0));
    int left = 0, right = n - 1, top = 0, bottom = n - 1;
    int num = 1;
    while (left <= right && top <= bottom) {
        for (int i = left; i <= right; i++) {
        matrix[top][i] = num++;
        }
        top++;
        for (int i = top; i <= bottom; i++) {
        matrix[i][right] = num++;
        }
        right--;
        if (top <= bottom) {
        for (int i = right; i >= left; i--) {
            matrix[bottom][i] = num++;
        }
        bottom--;
        }
        if (left <= right) {
        for (int i = bottom; i >= top; i--) {
            matrix[i][left] = num++;
        }
        left++;
        }
    }
    return matrix;
    }
}

结果

执行用时 : 296 ms, 击败 50.00% 使用 Dart 的用户

内存消耗 : 147.30 MB, 击败 -% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func generateMatrix(n int) [][]int {
	matrix := make([][]int, n)
	for i := range matrix {
		matrix[i] = make([]int, n)
	}
	left, right, top, bottom := 0, n-1, 0, n-1
	num := 1
	for left <= right && top <= bottom {
		for i := left; i <= right; i++ {
			matrix[top][i] = num
			num++
		}
		top++
		for i := top; i <= bottom; i++ {
			matrix[i][right] = num
			num++
		}
		right--
		if top <= bottom {
			for i := right; i >= left; i-- {
				matrix[bottom][i] = num
				num++
			}
			bottom--
		}
		if left <= right {
			for i := bottom; i >= top; i-- {
				matrix[i][left] = num
				num++
			}
			left++
		}
	}
	return matrix
}

结果

执行用时 : 1 ms, 击败 12.10% 使用 Go 的用户

内存消耗 : 2.02 MB, 击败 74.07% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# @param {Integer} n
# @return {Integer[][]}
def generate_matrix(n)
  matrix = Array.new(n) { Array.new(n, 0) }
  left, right, top, bottom = 0, n - 1, 0, n - 1
  num = 1
  while left <= right && top <= bottom
    left.upto(right) do |i|
      matrix[top][i] = num
      num += 1
    end
    top += 1
    top.upto(bottom) do |i|
      matrix[i][right] = num
      num += 1
    end
    right -= 1
    if top <= bottom
      right.downto(left) do |i|
        matrix[bottom][i] = num
        num += 1
      end
      bottom -= 1
    end
    if left <= right
      bottom.downto(top) do |i|
        matrix[i][left] = num
        num += 1
      end
      left += 1
    end
  end
  matrix
end

结果

执行用时 : 63 ms, 击败 66.67% 使用 Ruby 的用户

内存消耗 : 206.49 MB, 击败 33.33% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
object Solution {
    def generateMatrix(n: Int): Array[Array[Int]] = {
        val resultMatrix = new Array[Array[Int]](n)
        (0 until n).foreach { index =>
          resultMatrix(index) = new Array[Int](n)
        }
        val resultNum = n * n
        var rowBegin = 0
        var rowEnd = n - 1
        var columnBegin = 0
        var columnEnd = n - 1
        var insertNum = 1
        while (insertNum <= resultNum) {
          var columnTemp = columnBegin
          while (columnTemp <= columnEnd) {
            resultMatrix(rowBegin)(columnTemp) = insertNum
            insertNum += 1
            columnTemp += 1
          }
          rowBegin += 1
          var rowTemp = rowBegin
          while (rowTemp <= rowEnd) {
            resultMatrix(rowTemp)(columnEnd) = insertNum
            insertNum += 1
            rowTemp += 1
          }
          columnEnd -= 1
          columnTemp = columnEnd
          while (columnTemp >= columnBegin && rowEnd >= rowBegin) {
            resultMatrix(rowEnd)(columnTemp) = insertNum
            insertNum += 1
            columnTemp -= 1
          }
          rowEnd -= 1
          rowTemp = rowEnd
          while (rowTemp >= rowBegin && columnEnd >= columnBegin) {
            resultMatrix(rowTemp)(columnBegin) = insertNum
            insertNum += 1
            rowTemp -= 1
          }
          columnBegin += 1
        }
        resultMatrix
    }
}

结果

执行用时 : 428 ms, 击败 -% 使用 Scala 的用户

内存消耗 : 51.61 MB, 击败 -% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
impl Solution {
    pub fn generate_matrix(n: i32) -> Vec<Vec<i32>> {
        let mut result_matrix = vec![vec![0; n as usize]; n as usize];
        let mut insert_num = 1;
        let (mut row_begin, mut row_end, mut column_begin, mut column_end) = (0, n as usize - 1, 0, n as usize - 1);
        while insert_num <= n * n {
            for i in column_begin..=column_end {
                result_matrix[row_begin][i] = insert_num;
                insert_num += 1;
            }
            row_begin += 1;
            for i in row_begin..=row_end {
                result_matrix[i][column_end] = insert_num;
                insert_num += 1;
            }
            column_end -= 1;
            if row_begin <= row_end {
                for i in (column_begin..=column_end).rev() {
                    result_matrix[row_end][i] = insert_num;
                    insert_num += 1;
                }
                row_end -= 1;
            }
            if column_begin <= column_end {
                for i in (row_begin..=row_end).rev() {
                    result_matrix[i][column_begin] = insert_num;
                    insert_num += 1;
                }
                column_begin += 1;
            }
        }
        result_matrix
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.02 MB, 击败 65.00% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户