解題說明
Equal Row and Column Pairs
題目描述:給定 n×n 整數矩陣 grid,計算有多少對 (row_i, col_j) 使得第 i 行與第 j 列完全相等(元素逐一對應相同)。
解題思路:將每一行的元素序列轉換為可雜湊的鍵(如 vector<int> 或 string),用雜湊映射統計每種行模式出現次數。接著對每一列同樣建構序列,在映射中查詢該模式的出現次數,累加到答案中。時間複雜度 O(n²),因為每行每列都需要 O(n) 時間建構,共有 2n 條,再加上 O(n) 次查詢。
C++ 解法
複雜度分析
時間複雜度:O(n² log n) — 建構每個 row/col 向量各 O(n),共 2n 個;map 的插入和查詢各 O(n log n)(向量比較是 O(n),map 的 O(log n) 層)。若改用 unordered_map 配合字串鍵,可降至平均 O(n²)。
空間複雜度:O(n²) — 雜湊映射最多儲存 n 條行向量,每條長度 n。
虛擬碼
1. Build rowCount map: for each row, rowCount[row]++ 2. Initialize count = 0 3. For each column j (0 to n-1): a. Build col vector: col[i] = grid[i][j] b. count += rowCount[col] (0 if not found) 4. Return count
其他解法
字串序列化鍵:將 row/col 轉為逗號分隔字串(如 "1,2,3")存入 unordered_map<string, int>,查詢平均 O(n),整體 O(n²)。需小心用分隔符避免 "12,3" 和 "1,23" 衝突。
暴力 O(n³):對每一對 (i, j),逐元素比較 row_i 和 col_j,O(n) 比較,共 n² 對,整體 O(n³)。當 n 不大時可接受,但不如雜湊法高效。
延伸思考
- 若矩陣不是方陣(m×n),如何修改解法比較 m 行與 n 列?
- 若要同時找出所有配對的 (i, j) 索引(而非只計數),資料結構應如何調整?
- 如何高效地維護此計數,使其支援「更新單個格子值」的動態操作?