題目描述:設計一個資料結構,支援兩種操作:
add(point):將一個點加入資料結構(同一點可重複加入)。count(point):給定查詢點,計算能與資料結構中已有的點構成「軸對齊正方形」的方案總數(四個角點各選一個點,四邊平行於坐標軸)。解題思路:以查詢點 Q = (qx, qy) 為直角的其中一個頂點,列舉所有可能形成正方形的對角線。
正方形的對角線必須滿足:兩條對角線等長且平行於軸。固定 Q 後,對角頂點 D 的 x 座標必須不等於 qx(否則邊長為 0),且 |D.x - qx| == |D.y - qy|(正方形邊長相等)。
具體做法:
map<int, map<int, int>> 或 unordered_map 儲存每個點出現的次數 freq[x][y]。map<int, set<int>> 記錄每個 x 座標對應的所有 y 座標,方便枚舉。count(qx, qy):遍歷所有與 qx 不同的 x 座標 px,若 freq[px][qy] > 0,則邊長 side = |px - qx|,另兩角為 (qx, qy ± side) 和 (px, qy ± side),計算 freq[px][qy] * freq[qx][qy+side] * freq[px][qy+side] + freq[px][qy] * freq[qx][qy-side] * freq[px][qy-side] 並累加。時間複雜度:
add:O(1) 平均(雜湊表插入)。count:O(N) — N 為所有已加入的不同 x 座標數量,每個 x 做常數次查詢。空間複雜度:O(P) — P 為所有已加入點的總數(含重複),儲存在雜湊表中。
1. Data structures:
freq: map of (x -> map of (y -> count))
xToYs: map of (x -> set of y values)
2. add(x, y):
freq[x][y]++
xToYs[x].insert(y)
3. count(qx, qy):
total = 0
For each distinct px in xToYs where px != qx:
side = |px - qx|
For dy in [+side, -side]:
py = qy + dy
total += freq[px][qy] * freq[qx][py] * freq[px][py]
Return total二維頻率陣列 O(N):若座標範圍有限(本題 0–1000),可用二維整數陣列 cnt[1001][1001] 取代雜湊表,查詢時對所有 px 枚舉。存取速度更快(無雜湊碰撞),但固定佔用 O(1001²) 空間,不適合座標範圍大的情形。
列舉對角線法 O(N):對 count(qx, qy),直接遍歷所有已加入的點 p1,若 p1.x != qx 且 |p1.x - qx| == |p1.y - qy|,則 p1 與 Q 為正方形的對角,再用 freq 查詢另外兩角。邏輯等價於本解法,實作方式稍有不同。
count 操作改為計算矩形(不限正方形)的數量,解法需要哪些修改?freq[a] * freq[b] * freq[c])計數技巧,在哪些其他「計算圖形數量」的問題中也有類似應用?