九章演算法 | Google 面試題：矩形個數

來自專欄 九章演算法 - lintcode/leetcode題解

撰文 | JZ

專欄 | 九章演算法

題目描述

給一個二維數組構成的網格，其中的每一個格點非0即1。找出由4個不同格點上的1作為4個角，撐起的矩形個數。

注意：

1. 該矩形邊與橫軸或縱軸平行。

2. 只需要4個角有1即可。

3. 行數和列數範圍為[1, 200]

4. 一塊網格中1的總數不超過6000。

樣例:

輸入: [[1, 0, 0, 1, 0],

輸出: 1

解釋: 由於只有[1][2], [1][4], [3][2], [3][4]，這四個點能組成矩形。故輸出1。

輸入: [[1, 1, 1],

[1, 1, 1]]

輸出: 9

解釋: 有4個2x2的矩形，4個2x3的矩形，1個3x3的矩形。

輸入: [[1, 1, 1, 1]]

輸出: 0

解釋: 注意，四個角任意兩個不能共點

解題思路分析

最直觀的想法是窮舉所有的矩形，看其是否滿足要求。由於R行C列的網格，矩形一共有R * (R - 1) * C * (C - 1)個，所以窮舉的時間複雜度是O((R * C) ^ 2)，相當費時。有沒有什麼好的方法呢？

如果換一種思路考慮：每加入新的一行，會新加多少個矩形？這種想法有一些像動態規劃，複雜度會比窮舉法要低不少。由此就引出以下兩種方法：

方法一：

對於新行的每對1（記為cur_row[i]和cur_row[j]），新加矩形個數，是之前行row[i]= row[j] = 1出現的次數！所以逐行遍歷網格，並維護一個統計表count[i,j]（可用map實現，python中亦可用Counter或defaultdict實現），count記錄了之前行的每一對row[i] = row[j] = 1的次數。對於新行的每對1，例如cur_row[i]和cur_row[j]，最終結果加上count[i, j]，然後count[i, j]自增。

方法一複雜度分析：

時間複雜度：O(R ? C ^ 2)，其中R是行數，C是列數。由於遍歷每行當中都要尋找每對1，故每行遍歷複雜度為C ^ 2。

空間複雜度：O（C ^ 2)。

方法二（難度較大）：

在方法一中每一行都要O(C ^ 2)時間去遍歷，這個過程十分麻煩。很容易想到，可以先將每一行的所有1的位置記錄到列表當中，一共有R個這樣的列表。然後行遍歷過程中，直接對列表裡的每一對元素進行統計表count的查詢和自增即可。這是一種很好的辦法，但是如果這一行1很多，也即這一行很密集，那麼這個列表會很長，遍歷每一對元素複雜度仍然會逼近O(C ^ 2)。

針對這種密集的行（記該行為r），一種改進措施是不再遍歷其列表中每一對元素，而是直接尋找表中每一行（如行a）有多少個1，它們在r行對應列上也是1。假設有f個，那麼行a與行f所組成的矩形就有(f - 1) * f / 2個。我們可以用把行r的列錶轉換為集合Set，然後只需線性遍歷每一行，計算出f及其產生的矩形數。要注意如果如果行r和行a都是密集行，那麼行a只有在行r的下方有效。否則會重複計算，也即遍歷到行r計算了一次，遍歷到行a又計算了一次。

那麼到底一行超過多少個點算密集行，這裡取的是N ^ 0.5，也即根號N，其中N為網格中1的個數。這樣能保證最多只有N ^ 0.5個密集行，每一個密集行的複雜度為O(N)，故複雜度不超過N ^ 1.5。而對於稀疏行，因總點數不超過N，所以可證所有的稀疏行總共複雜度不超過N ^ 1.5（證明複雜，需用數學推導，這裡略去）。

方法二複雜度分析：

時間複雜度：由以上分析可得O(N ^ 1.5)。

空間複雜度：O(N + R + C ^ 2)。N是由於記錄1的位置的列表，R是由於由R個列表，C ^ 2是由於統計表count。

參考程序

http://www.jiuzhang.com/solution/number-of-corner-rectangles/

面試官角度分析

本題是一道稍難的統計類題目，很考驗面試者的觀察能力，改變統計的思路從而減小時間複雜度。同時這道題考察了對於Set、Map等數據結構的使用。如果能想到逐行添加的思路，進而給出方法一，可以給出Hire；如果能在方法一的基礎上進行優化，對於密集邊進行單獨處理並能分析出其複雜度，可以給出Strong Hire。

lintcode相關問題

連續子數組求和（中等）

http://www.lintcode.com/zh-cn/problem/continuous-subarray-sum/

最大矩形（困難）

http://www.lintcode.com/zh-cn/problem/maximal-rectangle/

推薦閱讀：