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

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

目录

问题

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

输入: 3

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

Given a positive integer n, generate a square matrix filled with elements from 1 to n^2n2 in spiral order.

Input: 3

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

示例

public class Program {

    public static void Main(string[] args) {
        var n = 3;

        var res = GenerateMatrix(n);
        ShowArray(res);

        Console.ReadKey();
    }

    private static void ShowArray(int[,] matrix) {
        for(var i = 0; i < matrix.GetLength(0); i++) {
            for(var j = 0; j < matrix.GetLength(1); j++) {
                Console.Write($"{matrix[i, j]} ");
            }
            Console.WriteLine();
        }
    }

    public static int[,] GenerateMatrix(int n) {
        var list = new List<int>();
        var max = (int)Math.Ceiling(n / 2d);
        var matrix = new int[n, n];
        var count = 0;
        Spiral(matrix, 0, n, n, max, ref count);
        return matrix;
    }

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

}

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

1 2 3
8 9 4
7 6 5

分析

显而易见, 以上算法的时间复杂度为:O(n^2)O(n2) 。

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

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

发表评论

登录后才能评论