蛇形矩陣生成算法詳解：從 O(n²) 到 O(n²/2) 的優化之路

什麼是蛇形矩陣？

5×5 示例：

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

規律：從左上角 (0,0) 起始，沿右上→左下對角線填數，方向交替（先下後上），形成「蛇形」軌跡。每條對角線稱為一「組」。

座標規律分析

左上半部（含主對角線）：行+列 = 組索引 i，偶數組列增行減，奇數組行增列減。
右下半部：行或列從 n-1 遞減，另一維從 i - n + 1 遞增。

算法一：標準單次遍歷 O(n²)

public static int[][] getGrid(int n) {
    int[][] a = new int[n][n];
    int m = 1;
    boolean isRow = false; // false: 偶組(列增行減), true: 奇組(行增列減)
    for (int i = 0; i < 2 * n - 1; i++) {
        int row = i;
        int minRow = (i < n) ? 0 : i - n + 1;
        while (row >= minRow) {
            if (row > n - 1) row = n - 1;
            int col = i - row;
            if (isRow) a[row][col] = m;
            else a[col][row] = m;
            m++;
            row--;
        }
        isRow = !isRow;
    }
    return a;
}

算法二：利用對稱性減半循環 O(n²/2)

觀察發現：位置 (r, c) 與 (n-1-r, n-1-c) 的數字之和恆為 n² + 1。只需填左上半部（含中線），右下半部由對稱性直接推導。

public static int[][] getGrid1(int n) {
    int[][] a = new int[n][n];
    int m = 1;
    int halfMax = (n * n + 1) / 2; // 奇數階含中心點
    int sum = n * n + 1;
    boolean isRow = false;
    for (int i = 0; m < halfMax; i++) {
        int row = i;
        while (row >= 0) {
            int col = i - row;
            if (col >= n) { row--; continue; } // 越界跳過
            if (isRow) {
                a[row][col] = m;
                a[n - 1 - row][n - 1 - col] = sum - m;
            } else {
                a[col][row] = m;
                a[n - 1 - col][n - 1 - row] = sum - m;
            }
            m++;
            if (m >= halfMax) break;
            row--;
        }
        isRow = !isRow;
    }
    return a;
}

效能對比與選擇建議

• 算法二循環次數減半，但單次迭代計算量增加（對稱座標計算、邊界判斷）。
• 實測現代 JVM 下兩者性能差異微乎其微，算法一可讀性更強，維護成本更低，推薦優先使用。
• 若極度追求極限性能（如嵌入式環境），可考慮算法二或進一步展開循環。

10×10 驗證輸出

 1  3  4 10 11 21 22 36 37 55
 2  5  9 12 20 23 35 38 54 56
 6  8 13 19 24 34 39 53 57 72
 7 14 18 25 33 40 52 58 71 73
15 17 26 32 41 51 59 70 74 85
16 27 31 42 50 60 69 75 84 86
28 30 43 49 61 68 76 83 87 94
29 44 48 62 67 77 82 88 93 95
45 47 63 66 78 81 89 92 96 99
46 64 65 79 80 90 91 97 98 100

歡迎各位大神分享更優雅的實現（任何語言均可）！