C#LeetCode刷题之#54-螺旋矩阵(Spiral Matrix)

C#LeetCode刷题之#54-螺旋矩阵(Spiral Matrix)

问题

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

输出: [1,2,3,6,9,8,7,4,5]

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]

输出: [1,2,3,4,8,12,11,10,9,5,6,7]

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

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Output: [1,2,3,6,9,8,7,4,5]

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]

Output: [1,2,3,4,8,12,11,10,9,5,6,7]

示例

public class Program {

    public static void Main(string[] args) {
        var matrix = new int[,] {
            { 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 }
        };

        var res = SpiralOrder(matrix);
        ShowArray(res);

        Console.ReadKey();
    }

    private static void ShowArray(IList<int> list) {
        foreach(var num in list) {
            Console.Write($"{num} ");
        }
        Console.WriteLine();
    }

    public static IList<int> SpiralOrder(int[,] matrix) {
        var list = new List<int>();
        var m = matrix.GetLength(0);
        var n = matrix.GetLength(1);
        var max = (int)Math.Ceiling(Math.Min(m, n) / 2d);
        Spiral(matrix, 0, m, n, max, ref list);
        return list;
    }

    private static void Spiral(int[,] matrix,
                               int level,
                               int m,
                               int n,
                               int max,
                               ref List<int> list) {
        if(level >= max) return;
        //顶端
        for(var j = level; j < n - level; j++) {
            list.Add(matrix[level, j]);
        }
        //右端
        for(var i = level + 1; i < m - level - 1; i++) {
            list.Add(matrix[i, n - level - 1]);
        }
        //底端
        if(level != m - level - 1) {
            for(var j = n - level - 1; j >= level; j--) {
                list.Add(matrix[m - level - 1, j]);
            }
        }
        //左端
        if(level != n - level - 1) {
            for(var i = m - level - 2; i >= level + 1; i--) {
                list.Add(matrix[i, level]);
            }
        }
        Spiral(matrix, ++level, m, n, max, ref list);
    }

}

以上给出1种算法实现,以下是这个案例的输出结果:

1 2 3 4 5 10 15 20 25 24 23 22 21 16 11 6 7 8 9 14 19 18 17 12 13

分析:

显而易见, 以上算法的时间复杂度为: O(m*n)

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3672

发表评论

登录后才能评论