題目網址：https://leetcode.cn/problems/detect-squares/

題意：給一在 X-Y 平面上的點所構成的 data stream。設計一個滿足下述要求的算法：

  • 新增一個在 data stream 中的新點到某個資料結構中。可以新增重覆的點, 並且會被視作不同的點
  • 給一查詢點, 從資料結構中選出三個點, 使這三點、查詢點構成一個面積為正的 axis-aligned square, 統計滿足該要求的方法數。

axis-aligned square 是一個正方形, 除了四條邊的長度相同外, 還滿足每條邊皆與 X軸 or Y軸 平行或垂直。

實現 DetectSquares class：

  • DetectSquares()：初始化 DetectSquares instance
  • void add(int[] point)：向資料結構新增一個新的點 point = [x, y]
  • int count(int[] point)：按上述方式統計與點 point = [x, y] 共同構成 axis-aligned square 的方法數

Solution：

想法：若要建構一正方形, 要先找出 query node 的對角線上的點 (x3, y3), 便能形成正方形 [(x1, y1), (x1, y3), (x3, y3), (x3, y1)]。首先一一遍歷所有 node, 然後找出滿足符合條件的 query node 的對角線上的點 (x3, y3), 並計算其方法數

class DetectSquares {
public:
    DetectSquares() {}

    void add(vector<int> point) {
        const int x = point[0], y = point[1];
        ++points[x][y]; // 新增重覆的點, 會被視作不同的點
    }

    int count(vector<int> point) {
        const int x1 = point[0], y1 = point[1], res = 0;

        for (auto x = points.begin(); x != points.end(); ++x) {
            const auto yPoints = x->second;

            for (auto y = yPoints.begin(); y != yPoints.end(); ++y) {
                const int x3 = x->first;
                const int y3 = y->first;

                // 若 (x3, y3) 不與 (x1, y1) 在同一 X軸 or Y軸上, 且邊的長度相同
                if (abs(x3 - x1) != 0 && abs(x3 - x1) == abs(y3 - y1)) {
                    res += (points[x3][y3] * points[x3][y1] * points[x1][y3]);
                }
            }
        }

        return res;
    }

private:
    // 一個 x 對應多個 y 點, e.g. (1, 3), (1, 4) 都會存在 x = 1  umap 中
    unordered_map<int, unordered_map<int, int>> points; // {x, {y, count}}
};
  • time：
    • DetectSquares()：$O(1)$
    • add()：$O(1)$
    • count()：$O(n^2)$ ➔ for loop 遍歷所有點, 其中 n 為點的個數
  • space：$O(n)$ ➔ points 紀錄每個點, 其中 n 為點的個數