LeetCode - Algorithms - 54. Spiral Matrix

Problem

54. Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Java

solution by myself

Although it is slow, it is pass on Leetcode by myself after attempting six times.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = m>0?matrix[0].length:0;
        List<Integer> list = new ArrayList<Integer>();
        for(int delta=0;delta<Math.ceil(Math.min(m, n)/2)+1;delta++) {
            for(int i=delta;m>=2*delta+1 && i<n-delta;i++) {
            	list.add(new Integer(matrix[delta][i]));
            }
            for(int i=delta+1;n>=2*delta+1 && i<m-delta;i++) {
            	list.add(new Integer(matrix[i][n-delta-1]));
            }
            for(int i=n-delta-2;m>=2*delta+2 && i>=delta;i--) {
            	list.add(new Integer(matrix[m-delta-1][i]));
            }
            for(int i=m-delta-2;n>=2*delta+2 && i>delta;i--) {
            	list.add(new Integer(matrix[i][delta]));
            } 	
        }
        return list;        
    }
}

Submission Detail

  • 22 / 22 test cases passed.
  • Runtime: 1 ms, faster than 6.37% of Java online submissions for Spiral Matrix.
  • Memory Usage: 34.4 MB, less than 100.00% of Java online submissions for Spiral Matrix.

better solution

盘点今年秋招那些“送命”的算法面试题 - 极客大学

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
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
		List<Integer> result = new ArrayList<>();
		int height = matrix.length, width = height == 0 ? 0 : matrix[0].length;
		int size = height * width;

		int[] dirX = { 0, 1, 0, -1 };
		int[] dirY = { 1, 0, -1, 0 };

		int x = 0, y = -1, dir = 0;
		for (int step, total = 0; total < size; total += step) {
			if (dir == 0 || dir == 2) {
				step = width;
				height--;
			} else {
				step = height;
				width--;
			}
			for (int i = step; i > 0; i--) {
				x += dirX[dir];
				y += dirY[dir];
				result.add(matrix[x][y]);
			}
			dir = ++dir % 4;
		}
		return result;       
    }
}

Submission Detail

  • 22 / 22 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Spiral Matrix.
  • Memory Usage: 34.2 MB, less than 100.00% of Java online submissions for Spiral Matrix.

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
public class Solution {
    public IList<int> SpiralOrder(int[][] matrix) {
            IList<int> list = new List<int>();
            int height = matrix.Length;
            int width = height == 0 ? 0 : matrix[0].Length;
            int size = height * width;

            int[] dirX = { 0, 1, 0, -1 };
            int[] dirY = { 1, 0, -1, 0 };

            int x = 0, y = -1, dir = 0;
            for (int step, total = 0; total < size; total += step)
            {
                if (dir == 0 || dir == 2)
                {
                    step = width;
                    height--;
                }
                else
                {
                    step = height;
                    width--;
                }
                for (int i = step; i > 0; i--)
                {
                    x += dirX[dir];
                    y += dirY[dir];
                    list.Add(matrix[x][y]);
                }
                dir = ++dir % 4;
            }

            return list;        
    }
}

Submission Detail

  • 23 / 23 test cases passed.
  • Runtime: 176 ms, faster than 71.81% of C# online submissions for Spiral Matrix.
  • Memory Usage: 40.5 MB, less than 95.65% of C# online submissions for Spiral Matrix.