Q003_dploop_solution

[rbee3u]

Question_ID: Q003

Language: Python3

Time Cost: 卡在去找低于平方的算法，远远超过40分钟了

Time Complexity: O(n^2)

Solution

1. 维护一个存储矩形的字典rect_dict和一个存储相交关系的集合edge_set；
2. 每次先添加一个矩形，然后不断从相交集合中取出一对矩形进行合并，删除原来的两个矩形，添加合并后的矩形，直至集合为空。如果取出的一对矩形中至少有一个之前已经被合并过了，则本次合并操作取消。由于合并次数是O(n)的，每次合并后去遍历查询哪些相交也是O(n)的，整个合并的过程是O(n^2)。剩下一个问题就是从相交集合中取出矩形对的次数，可以考虑取出次数等于添加进去的次数，而每次合并添加的次数也是O(n)的，因此取出矩形对的次数也是O(n^2)的；
3. 综上，总的时间复杂度是O(n^2)的(这里把字典与集合的增删查改视为O(1))。

My Code

# coding: utf-8
class Solution(object):

    def __init__(self):
        pass

    def maximumRectangles(self, rect_list):

        rect_dict, edge_set, counter = {}, set(), 0

        def is_disjoint(u, v): # 判断矩形相离 O(1)
            return u[0] < v[1] or v[0] < u[1] \
                or u[3] < v[2] or v[3] < u[2]

        def minimum_covering(u, v): # 矩形合并 O(1)
            return [ max(u[0], v[0]), min(u[1], v[1]) \
                   , min(u[2], v[2]), max(u[3], v[3]) ]

        def add_rect(u): # 添加矩形 O(n)
            nonlocal rect_dict, edge_set, counter
            for k, v in rect_dict.items():
                if not is_disjoint(u, v):
                    edge_set.add((k, counter))
            rect_dict[counter] = u; counter += 1

        for u in rect_list:
            add_rect(u)
            while len(edge_set) > 0:
                (ka, kb) = edge_set.pop()
                if (ka not in rect_dict) or (kb not in rect_dict):
                    continue
                add_rect(minimum_covering(                       \
                            rect_dict.pop(ka), rect_dict.pop(kb)))
        return list(rect_dict.values())

if __name__ == '__main__':
    rect_list = [
        [1, 0, 0, 1],
        [1, 0, 4, 5],
        [3, 2, 2, 5],
        [2, 1, 5, 6]
    ]
    sol = Solution()
    ret = sol.maximumRectangles(rect_list)
    print(ret)

Other

[rbee3u]

edge_set 其实是没有必要的，每次添加前从当前集合中遍历就行了，加了它反而显得复杂了些。

[rbee3u]

强迫症再来提交一发简洁一些的答案

# coding: utf-8
class Solution(object):

    def __init__(self):
        pass

    def maximumRectangles(self, rects):

        def do_covering(x, y):
            (xu, xd, xl, xr), (yu, yd, yl, yr) = x, y
            if xu<yd or yu<xd or xr<yl or yr<xl:
                return None
            return ( max(xu, yu), min(xd, yd) \
                   , min(xl, yl), max(xr, yr) )

        result, length = [x for x in rects], len(rects)

        i = 0
        while i < length:
            for j in range(i):
                temp = do_covering(result[i], result[j])
                if temp:
                    result[i] = temp
                    del result[j]
                    i = i - 2
                    length = length - 1
                    break
            i = i + 1

        return result

if __name__ == '__main__':
    rect_list = [
        (1, 0, 0, 1),
        (1, 0, 4, 5),
        (3, 2, 2, 5),
        (2, 1, 5, 6)
    ]
    sol = Solution()
    ret = sol.maximumRectangles(rect_list)
    print(ret)

[isaacpei]

前面的没太看懂容我回去瞅瞅, 简洁版简单易懂赞赞赞 唯一的建议就是别把多行逻辑写一行, 虽然这样好看一些

[rbee3u]

@isaacpei 好好好 = =，，，强迫惯了，多行写一行确实坑，我改一下

[biganans]

先赞后看