每日一題——Python實現PAT乙級1050 螺旋矩陣（舉一反三+思想解讀+逐步優化）6千字好文

一個認為一切根源都是“自己不夠強”的INTJ

個人主頁：用哲學編程-CSDN博客
專欄：每日一題——舉一反三
Python編程學習
Python內置函數

Python-3.12.0文檔解讀

我的寫法

時間復雜度分析

空間復雜度分析

總結

我要更強

代碼解釋

時間復雜度

空間復雜度

總結

哲學和編程思想

哲學思想

編程思想

總結

舉一反三

1. 模塊化設計

2. 抽象化

3. 迭代與遞歸

4. 算法優化

5. 數據結構選擇

6. 邊界條件處理

7. 簡約主義

8. 秩序與結構

題目鏈接：https://pintia.cn/problem-sets/994805260223102976/exam/problems/type/7?problemSetProblemId=994805275146436608&page=0

我的寫法

import math# 讀取矩陣元素的數量
N = int(input())
# 讀取數字列表并按降序排序
nums = list(map(int, input().split()))
nums.sort(reverse=True)def find_dimensions(N):# 找到最接近N的平方根的整數middle = math.isqrt(N)# 從middle開始向上找，直到找到兩個數乘積為Nfor i in range(middle, N+1):for j in range(middle, 0, -1):if i * j == N:return i, jdef create_spiral_matrix(N, nums, m, n, seq_paces):# 初始化矩陣matrix = [[0 for i in range(n)] for j in range(m)]index_matrix = [0, -1]  # 矩陣索引初始位置index_nums = 0  # 數字列表索引for i in range(len(seq_paces)):if i % 4 == 0:  # 向右移動seq_paces[i]步index_matrix[1] += 1for j in range(seq_paces[i]):matrix[index_matrix[0]][index_matrix[1] + j] = nums[index_nums]if j == seq_paces[i] - 1:index_matrix[1] = index_matrix[1] + jindex_nums += 1elif i % 4 == 1:  # 向下移動seq_paces[i]步index_matrix[0] += 1for j in range(seq_paces[i]):matrix[index_matrix[0] + j][index_matrix[1]] = nums[index_nums]if j == seq_paces[i] - 1:index_matrix[0] = index_matrix[0] + jindex_nums += 1elif i % 4 == 2:  # 向左移動seq_paces[i]步index_matrix[1] -= 1for j in range(seq_paces[i]):matrix[index_matrix[0]][index_matrix[1] - j] = nums[index_nums]if j == seq_paces[i] - 1:index_matrix[1] = index_matrix[1] - jindex_nums += 1elif i % 4 == 3:  # 向上移動seq_paces[i]步index_matrix[0] -= 1for j in range(seq_paces[i]):matrix[index_matrix[0] - j][index_matrix[1]] = nums[index_nums]if j == seq_paces[i] - 1:index_matrix[0] = index_matrix[0] - jindex_nums += 1return matrixdef calculate_sequence_paces(N, m, n):# 計算螺旋填充的步數序列if m == 1:return [n]elif n == 1:return [1, m - 1]seq_paces = []dif = 0for i in range(N):if i == 0:seq_paces.append(n)dif += 1continueif i % 2 == 1:seq_paces.append(m - dif)elif i % 2 == 0:seq_paces.append(n - dif)dif += 1if seq_paces[-1] == 0:return seq_paces[:-1]return seq_paces# 找到矩陣的維度
m, n = find_dimensions(N)
# 計算螺旋填充的步數序列
seq_paces = calculate_sequence_paces(N, m, n)
# 創建螺旋矩陣
matrix = create_spiral_matrix(N, nums, m, n, seq_paces)
# 輸出矩陣
for row in matrix:print(*row)

時間復雜度分析

排序：對?N?個數字進行排序的時間復雜度是?O(N log N)。
find_dimensions：這個函數在最壞情況下需要檢查大約?sqrt(N)?個可能的行和列組合，因此時間復雜度大約是?O(N)。
calculate_sequence_paces：這個函數在最壞情況下需要遍歷?N?次，時間復雜度也是?O(N)。
create_spiral_matrix：這個函數需要遍歷所有步數序列，步數序列的長度大約是?sqrt(N)，每次填充矩陣的時間復雜度是?O(N)，所以總時間復雜度也是?O(N)。

綜合來看，主要的時間消耗來自于排序和矩陣填充，因此總時間復雜度是 O(N log N)。

空間復雜度分析

排序：排序需要的額外空間復雜度是?O(N)。
矩陣：矩陣的大小是?O(N)。
步數序列：步數序列的大小大約是?sqrt(N)。

綜合來看，主要的空間消耗來自于矩陣和排序，因此總空間復雜度是 O(N)。

總結

這段代碼在功能上實現了將一組數字按螺旋順序填充到矩陣中，并且在時間和空間復雜度上都是高效的。代碼結構清晰，函數職責明確，易于理解和維護。主要的時間消耗來自于排序和矩陣填充，而空間消耗主要由矩陣和排序決定。總體來說，這是一段設計良好且高效的代碼。

我要更強

為了解決這個問題，我們需要完成以下步驟：

讀取輸入的數字數量?N?和數字列表。
對數字列表進行降序排序。
找到滿足?m * n = N?且?m >= n?的矩陣維度?m?和?n，并且使得?m - n?最小。
創建一個空的螺旋矩陣，并按照順時針方向填充數字。
輸出填充好的螺旋矩陣。

以下是實現上述步驟的Python代碼：

import math# 讀取輸入
N = int(input())
nums = list(map(int, input().split()))# 對數字列表進行降序排序
nums.sort(reverse=True)# 找到合適的矩陣維度
def find_dimensions(N):min_diff = float('inf')m, n = 0, 0for i in range(1, int(math.sqrt(N)) + 1):if N % i == 0:j = N // iif j >= i and j - i < min_diff:min_diff = j - im, n = j, ireturn m, nm, n = find_dimensions(N)# 創建并填充螺旋矩陣
matrix = [[0] * n for _ in range(m)]
top, bottom, left, right = 0, m - 1, 0, n - 1
index = 0while top <= bottom and left <= right:# 向右填充for i in range(left, right + 1):matrix[top][i] = nums[index]index += 1top += 1# 向下填充for i in range(top, bottom + 1):matrix[i][right] = nums[index]index += 1right -= 1# 向左填充if top <= bottom:for i in range(right, left - 1, -1):matrix[bottom][i] = nums[index]index += 1bottom -= 1# 向上填充if left <= right:for i in range(bottom, top - 1, -1):matrix[i][left] = nums[index]index += 1left += 1# 輸出螺旋矩陣
for row in matrix:print(' '.join(map(str, row)))

代碼解釋

輸入讀取：首先讀取輸入的數字數量?N?和數字列表?nums。
排序：對數字列表?nums?進行降序排序。
找到矩陣維度：定義?find_dimensions?函數來找到合適的矩陣維度?m?和?n，使得?m * n = N?且?m >= n，并且?m - n?最小。
填充矩陣：創建一個空的矩陣?matrix，并使用邊界指針（top,?bottom,?left,?right）來控制填充方向，按照順時針方向填充數字。
輸出矩陣：最后，輸出填充好的螺旋矩陣。

這個代碼在時間和空間復雜度上都是高效的，并且能夠正確地解決給定的問題。

代碼結構和邏輯

輸入處理：代碼首先讀取輸入的數字數量 N 和數字列表 nums，這一部分的時間復雜度是 O(N)，因為需要讀取和存儲 N 個數字。
排序：對數字列表 nums 進行降序排序，使用的是 Python 內置的 sort 方法，其時間復雜度是 O(N log N)。
找到矩陣維度：定義 find_dimensions 函數來找到合適的矩陣維度 m 和 n。這個函數的時間復雜度是 O(sqrt(N))，因為它只需要遍歷到 sqrt(N) 的整數。
填充矩陣：創建一個空的矩陣 matrix，并使用邊界指針（top, bottom, left, right）來控制填充方向，按照順時針方向填充數字。這一部分的時間復雜度是 O(N)，因為每個數字只被處理一次。
輸出矩陣：最后，輸出填充好的螺旋矩陣。這一部分的時間復雜度也是 O(N)，因為需要遍歷并輸出每個元素。

時間復雜度

綜合以上分析，主要的時間消耗來自于排序和矩陣填充。因此，總的時間復雜度是 O(N log N)。

空間復雜度

輸入存儲：需要存儲?N?個數字，空間復雜度是?O(N)。
排序：排序過程中需要額外的空間，但由于 Python 的?sort?方法是原地排序，所以這部分的空間復雜度可以忽略不計。
矩陣存儲：需要存儲一個?m * n?的矩陣，空間復雜度是?O(N)。

因此，總的空間復雜度是 O(N)。

總結

這段代碼在功能上實現了將一組數字按螺旋順序填充到矩陣中，并且在時間和空間復雜度上都是高效的。代碼結構清晰，函數職責明確，易于理解和維護。主要的時間消耗來自于排序和矩陣填充，而空間消耗主要由矩陣和輸入數據決定。總體來說，這是一段設計良好且高效的代碼。

哲學和編程思想

這段代碼體現了多個哲學和編程思想，以下是一些主要的思想：

哲學思想

秩序與結構：哲學上，秩序和結構是宇宙的基本原則。這段代碼通過將無序的數字列表轉換為有序的螺旋矩陣，體現了對秩序和結構的追求。
簡約主義：代碼盡量保持簡潔和高效，避免不必要的復雜性。這種簡約主義的思想在代碼的結構和邏輯中得到了體現。

編程思想

模塊化：代碼被劃分為多個函數，每個函數負責一個特定的任務（如輸入處理、排序、找到矩陣維度、填充矩陣和輸出矩陣）。這種模塊化的設計使得代碼更易于理解和維護。
抽象化：通過定義 find_dimensions 函數來抽象出找到矩陣維度的邏輯，使得主邏輯更加簡潔。這種抽象化的思想有助于隱藏復雜性，提高代碼的可讀性。
迭代與遞歸：雖然代碼中沒有顯式的遞歸，但通過邊界指針的迭代方式來填充矩陣，體現了迭代思想。迭代是一種逐步推進的解決問題的方法，適用于處理有序數據。
算法優化：在找到矩陣維度的過程中，代碼通過遍歷到 sqrt(N) 的整數來減少計算量，體現了算法優化的思想。這種優化減少了不必要的計算，提高了效率。
數據結構選擇：代碼選擇了列表和二維列表（矩陣）作為主要的數據結構，這種選擇是基于問題的需求和數據結構的特性。合理選擇數據結構是編程中的重要思想。
邊界條件處理：在填充矩陣的過程中，代碼通過邊界指針來控制填充方向，并處理邊界條件。這種對邊界條件的細致處理是編程中的重要思想，有助于避免錯誤和提高代碼的健壯性。