力扣00054.螺旋矩阵

发表于 分类于 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 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] <= 100

解决方法

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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        if (matrix.empty()) {
            return result;
        }
        int m = matrix.size();
        int n = matrix[0].size();
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; ++j) {
                result.push_back(matrix[top][j]);
            }
            top++;
            for (int i = top; i <= bottom; ++i) {
                result.push_back(matrix[i][right]);
            }
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; --j) {
                    result.push_back(matrix[bottom][j]);
                }
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; --i) {
                    result.push_back(matrix[i][left]);
                }
                left++;
            }
        }
        return result;
    }
};

结果

执行用时 : 3 ms, 击败 30.31% 使用 C++ 的用户

内存消耗 : 8.05 MB, 击败 14.60% 使用 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
27
28
29
30
31
32
33
34
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; ++j) {
                result.add(matrix[top][j]);
            }
            top++;
            for (int i = top; i <= bottom; ++i) {
                result.add(matrix[i][right]);
            }
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; --j) {
                    result.add(matrix[bottom][j]);
                }
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; --i) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }
        return result;
    }
}

结果

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

内存消耗 : 40.52 MB, 击败 34.74% 使用 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 spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        result = []
        if not matrix:
            return result
        m, n = len(matrix), len(matrix[0])
        top, bottom, left, right = 0, m - 1, 0, n - 1
        while top <= bottom and left <= right:
            for j in range(left, right + 1):
                result.append(matrix[top][j])
            top += 1
            for i in range(top, bottom + 1):
                result.append(matrix[i][right])
            right -= 1
            if top <= bottom:
                for j in range(right, left - 1, -1):
                    result.append(matrix[bottom][j])
                bottom -= 1
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    result.append(matrix[i][left])
                left += 1
        return result

结果

执行用时 : 10 ms, 击败 89.47% 使用 Python 的用户

内存消耗 : 11.34 MB, 击败 94.82% 使用 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 spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        result = []
        if not matrix:
            return result
        m, n = len(matrix), len(matrix[0])
        top, bottom, left, right = 0, m - 1, 0, n - 1
        while top <= bottom and left <= right:
            for j in range(left, right + 1):
                result.append(matrix[top][j])
            top += 1
            for i in range(top, bottom + 1):
                result.append(matrix[i][right])
            right -= 1
            if top <= bottom:
                for j in range(right, left - 1, -1):
                    result.append(matrix[bottom][j])
                bottom -= 1
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    result.append(matrix[i][left])
                left += 1
        return result

结果

执行用时 : 33 ms, 击败 84.52% 使用 Python3 的用户

内存消耗 : 16.41 MB, 击败 52.20% 使用 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
38
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    if (matrix == NULL || matrixSize == 0 || matrixColSize == NULL || matrixColSize[0] == 0) {
        *returnSize = 0;
        return NULL;
    }
    int m = matrixSize;
    int n = matrixColSize[0];
    int* result = (int*)malloc(m * n * sizeof(int));
    *returnSize = m * n;
    int top = 0, bottom = m - 1, left = 0, right = n - 1;
    int index = 0;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; ++j) {
            result[index++] = matrix[top][j];
        }
        top++;
        for (int i = top; i <= bottom; ++i) {
            result[index++] = matrix[i][right];
        }
        right--;
        if (top <= bottom) {
            for (int j = right; j >= left; --j) {
                result[index++] = matrix[bottom][j];
            }
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; --i) {
                result[index++] = matrix[i][left];
            }
            left++;
        }
    }
    return result;
}

结果

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

内存消耗 : 5.34 MB, 击败 94.98% 使用 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
30
31
32
33
34
public class Solution {
    public IList<int> SpiralOrder(int[][] matrix) {
        List<int> result = new List<int>();
        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) {
            return result;
        }
        int m = matrix.Length;
        int n = matrix[0].Length;
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; ++j) {
                result.Add(matrix[top][j]);
            }
            top++;
            for (int i = top; i <= bottom; ++i) {
                result.Add(matrix[i][right]);
            }
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; --j) {
                    result.Add(matrix[bottom][j]);
                }
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; --i) {
                    result.Add(matrix[i][left]);
                }
                left++;
            }
        }
        return result;
    }
}

结果

执行用时 : 105 ms, 击败 55.06% 使用 C# 的用户

内存消耗 : 45.40 MB, 击败 5.66% 使用 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
29
30
31
32
33
34
35
36
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    let result = [];
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
        return result;
    }
    let m = matrix.length;
    let n = matrix[0].length;
    let top = 0, bottom = m - 1, left = 0, right = n - 1;
    while (top <= bottom && left <= right) {
        for (let j = left; j <= right; ++j) {
            result.push(matrix[top][j]);
        }
        top++;
        for (let i = top; i <= bottom; ++i) {
            result.push(matrix[i][right]);
        }
        right--;
        if (top <= bottom) {
            for (let j = right; j >= left; --j) {
                result.push(matrix[bottom][j]);
            }
            bottom--;
        }
        if (left <= right) {
            for (let i = bottom; i >= top; --i) {
                result.push(matrix[i][left]);
            }
            left++;
        }
    }
    return result;
};

结果

执行用时 : 48 ms, 击败 97.03% 使用 JavaScript 的用户

内存消耗 : 48.98 MB, 击败 21.36% 使用 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
25
26
27
28
29
30
31
32
function spiralOrder(matrix: number[][]): number[] {
    let result: number[] = [];
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
        return result;
    }
    let m: number = matrix.length;
    let n: number = matrix[0].length;
    let top: number = 0, bottom: number = m - 1, left: number = 0, right: number = n - 1;
    while (top <= bottom && left <= right) {
        for (let j = left; j <= right; ++j) {
            result.push(matrix[top][j]);
        }
        top++;
        for (let i = top; i <= bottom; ++i) {
            result.push(matrix[i][right]);
        }
        right--;
        if (top <= bottom) {
            for (let j = right; j >= left; --j) {
                result.push(matrix[bottom][j]);
            }
            bottom--;
        }
        if (left <= right) {
            for (let i = bottom; i >= top; --i) {
                result.push(matrix[i][left]);
            }
            left++;
        }
    }
    return result;
}

结果

执行用时 : 60 ms, 击败 70.37% 使用 TypeScript 的用户

内存消耗 : 50.38 MB, 击败 10.70% 使用 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
32
33
34
35
36
37
38
39
40
41
42
class Solution {

    /**
     * @param Integer[][] $matrix
     * @return Integer[]
     */
    function spiralOrder($matrix) {
        $result = [];
        if ($matrix === null || empty($matrix) || empty($matrix[0])) {
            return $result;
        }
        $m = count($matrix);
        $n = count($matrix[0]);
        $top = 0;
        $bottom = $m - 1;
        $left = 0;
        $right = $n - 1;
        while ($top <= $bottom && $left <= $right) {
            for ($j = $left; $j <= $right; ++$j) {
                $result[] = $matrix[$top][$j];
            }
            $top++;
            for ($i = $top; $i <= $bottom; ++$i) {
                $result[] = $matrix[$i][$right];
            }
            $right--;
            if ($top <= $bottom) {
                for ($j = $right; $j >= $left; --$j) {
                    $result[] = $matrix[$bottom][$j];
                }
                $bottom--;
            }
            if ($left <= $right) {
                for ($i = $bottom; $i >= $top; --$i) {
                    $result[] = $matrix[$i][$left];
                }
                $left++;
            }
        }
        return $result;
    }
}

结果

执行用时 : 6 ms, 击败 64.29% 使用 PHP 的用户

内存消耗 : 20.27 MB, 击败 7.14% 使用 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
class Solution {
    func spiralOrder(_ matrix: [[Int]]) -> [Int] {
       var result = [matrix[0][0]], a = 0, b = 0, arrow = "right",
            leftmin = 0, rightmax = matrix[0].count - 1,
            upmin = 0, downmax = matrix.count - 1
        if matrix[0].count == 1 { arrow = "down" }
        while result.count < matrix.count * matrix[0].count {
            if arrow == "right" {
                b += 1
                if b == rightmax {
                    upmin += 1
                    arrow = "down"
                }
            } else if arrow == "down" {
                a += 1
                if a == downmax {
                    rightmax -= 1
                    arrow = "left"
                }
            } else if arrow == "left" {
                b -= 1
                if b == leftmin {
                    downmax -= 1
                    arrow = "up"
                }
            } else if arrow == "up" {
                a -= 1
                if a == upmin {
                    leftmin += 1
                    arrow = "right"
                }
            }
            result.append(matrix[a][b])
        }
        return result
    }
}

结果

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

内存消耗 : 15.66 MB, 击败 15.00% 使用 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
34
35
class Solution {
    fun spiralOrder(matrix: Array<IntArray>): List<Int> {
        val result = mutableListOf<Int>()
        if (matrix.isEmpty() || matrix[0].isEmpty()) {
            return result
        }
        var top = 0
        var bottom = matrix.size - 1
        var left = 0
        var right = matrix[0].size - 1
        while (top <= bottom && left <= right) {
            for (i in left..right) {
                result.add(matrix[top][i])
            }
            top++
            for (i in top..bottom) {
                result.add(matrix[i][right])
            }
            right--
            if (top <= bottom) {
                for (i in right downTo left) {
                    result.add(matrix[bottom][i])
                }
                bottom--
            }
            if (left <= right) {
                for (i in bottom downTo top) {
                    result.add(matrix[i][left])
                }
                left++
            }
        }
        return result
    }
}

结果

执行用时 : 148 ms, 击败 71.93% 使用 Kotlin 的用户

内存消耗 : 33.81 MB, 击败 28.07% 使用 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
31
32
33
class Solution {
  List<int> spiralOrder(List<List<int>> matrix) {
    List<int> result = [];
    if (matrix.isEmpty || matrix[0].isEmpty) {
        return result;
    }
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (int i = left; i <= right; i++) {
        result.add(matrix[top][i]);
        }
        top++;
        for (int i = top; i <= bottom; i++) {
        result.add(matrix[i][right]);
        }
        right--;
        if (top <= bottom) {
        for (int i = right; i >= left; i--) {
            result.add(matrix[bottom][i]);
        }
        bottom--;
        }
        if (left <= right) {
        for (int i = bottom; i >= top; i--) {
            result.add(matrix[i][left]);
        }
        left++;
        }
    }
    return result;
    }
}

结果

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

内存消耗 : 142.05 MB, 击败 100.00% 使用 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
func spiralOrder(matrix [][]int) []int {
    result := []int{}
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return result
    }
    top, bottom := 0, len(matrix)-1
    left, right := 0, len(matrix[0])-1
    for top <= bottom && left <= right {
        for i := left; i <= right; i++ {
            result = append(result, matrix[top][i])
        }
        top++
        for i := top; i <= bottom; i++ {
            result = append(result, matrix[i][right])
        }
        right--
        if top <= bottom {
            for i := right; i >= left; i-- {
                result = append(result, matrix[bottom][i])
            }
            bottom--
        }
        if left <= right {
            for i := bottom; i >= top; i-- {
                result = append(result, matrix[i][left])
            }
            left++
        }
    }
    return result
}

结果

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

内存消耗 : 1.86 MB, 击败 55.24% 使用 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
# @param {Integer[][]} matrix
# @return {Integer[]}
def spiral_order(matrix)
  result = []
  return result if matrix.empty? || matrix[0].empty?
  top, bottom = 0, matrix.length - 1
  left, right = 0, matrix[0].length - 1
  while top <= bottom && left <= right
    left.upto(right) do |i|
      result.push(matrix[top][i])
    end
    top += 1
    top.upto(bottom) do |i|
      result.push(matrix[i][right])
    end
    right -= 1
    if top <= bottom
      right.downto(left) do |i|
        result.push(matrix[bottom][i])
      end
      bottom -= 1
    end
    if left <= right
      bottom.downto(top) do |i|
        result.push(matrix[i][left])
      end
      left += 1
    end
  end
  result
end

结果

执行用时 : 74 ms, 击败 0.00% 使用 Ruby 的用户

内存消耗 : 206.35 MB, 击败 14.29% 使用 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
object Solution {
  def spiralOrder(matrix: Array[Array[Int]]): List[Int] = {
    var result: List[Int] = List()
    if (matrix.isEmpty || matrix(0).isEmpty) {
      return result
    }
    var top = 0
    var bottom = matrix.length - 1
    var left = 0
    var right = matrix(0).length - 1
    while (top <= bottom && left <= right) {
      for (i <- left to right) {
        result :+= matrix(top)(i)
      }
      top += 1
      for (i <- top to bottom) {
        result :+= matrix(i)(right)
      }
      right -= 1
      if (top <= bottom) {
        for (i <- right to left by -1) {
          result :+= matrix(bottom)(i)
        }
        bottom -= 1
      }
      if (left <= right) {
        for (i <- bottom to top by -1) {
          result :+= matrix(i)(left)
        }
        left += 1
      }
    }
    result
  }
}

结果

执行用时 : 439 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 54.64 MB, 击败 25.00% 使用 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
impl Solution {
    pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
        let (rows, cols) = (matrix.len(), matrix[0].len());
        let mut visited = vec![vec![false; cols]; rows];
        let total = rows * cols;
        let mut order = vec![0; total];
        let directions: Vec<Vec<i32>> = vec![vec![0, 1], vec![1, 0], vec![0, -1], vec![-1, 0]];
        let mut direction_idx = 0;
        let (mut row, mut col) = (0, 0);
        for i in 0..total {
            order[i] = matrix[row][col];
            visited[row][col] = true;
            let next_row = row as i32 + directions[direction_idx][0];
            let next_col = col as i32 + directions[direction_idx][1];
            if next_row < 0
                || next_row >= rows as i32
                || next_col < 0
                || next_col >= cols as i32
                || visited[next_row as usize][next_col as usize]
            {
                direction_idx = (direction_idx + 1) % 4;
            }
            row = (row as i32 + directions[direction_idx][0]) as usize;
            col = (col as i32 + directions[direction_idx][1]) as usize;
        }
        order
    }
}

结果

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

内存消耗 : 2.09 MB, 击败 39.19% 使用 Rust 的用户

Racket

暂时未解决

1

结果

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

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

Erlang

暂时未解决

1

结果

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

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

Elixir

暂时未解决

1

结果

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

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