Wednesday, September 26, 2018

[LeetCode]Rectangle Area II


这道题Brute Force的做法不难想，我们把矩形分解成1x1的小矩形，用一个二维数组表示对应的单位矩形是否出现过，然后算总面积即可。但是显而易见这个方法时间复杂度过于高，并不适用。
但是这个方法可以提供一个很好的思路，我们可以把输入的点压缩一下来优化一下时间复杂度。比如说如果x轴上的点出现了[2, 5, 30, 200, 3200]，我们可以将其映射到[0, 1, 2, 3, 4]的区间，这样我们仍然是算有多少个1x1个小矩形，但是算面积的时候，再把对应[1, N]区间的数map回原坐标计算面积即可。假设输入有N个矩形，时间复杂度O(N^3)，空间复杂度O(N^2), 代码如下：

class Solution {
public:
int rectangleArea(vector<vector<int>>& rectangles) {
const int MOD = 1000000007;
unordered_set<int> setX, setY;
for (const auto& rectangle : rectangles)
{
int x1 = rectangle[0], x2 = rectangle[2], y1 = rectangle[1], y2 = rectangle[3];
setX.insert(x1);
setX.insert(x2);
setY.insert(y1);
setY.insert(y2);
}
vector<int> xs, ys;
for (const auto& x : setX)xs.push_back(x);
for (const auto& y : setY)ys.push_back(y);
sort(xs.begin(), xs.end());
sort(ys.begin(), ys.end());
int lenX = xs.size(), lenY = ys.size();
unordered_map<int, int> mapX, mapY;
for (int i = 0; i < lenX; ++i)mapX[xs[i]] = i;
for (int i = 0; i < lenY; ++i)mapY[ys[i]] = i;
vector<vector<bool>> grid(lenY - 1, vector<bool>(lenX - 1, false));
for (const auto& rect : rectangles)
{
int minX = mapX[rect[0]], maxX = mapX[rect[2]], minY = mapY[rect[1]], maxY = mapY[rect[3]];
for (int i = minY; i < maxY; ++i)
for (int j = minX; j < maxX; ++j)
grid[i][j] = true;
}
long area = 0;
for (int i = 0; i < lenY - 1; ++i)
{
for (int j = 0; j < lenX - 1; ++j)
{
if (grid[i][j])
{
area += static_cast<long>(ys[i + 1] - ys[i]) * (xs[j + 1] - xs[j]);
area %= MOD;
}
}
}
return area;
}
};
view raw Rectangle Area II_idx_compression.cpp hosted with ❤ by GitHub


除此之外，如果我们想象一根平行于x轴的直线从最底端向上扫，我们可以得到所有矩形在不同y坐标下在x轴的映射。我们可以根据每个单位长度y下，矩形在x轴上映射的长度的和来算出总的矩形的面积。所以现在的问题是，如果算出矩形在x轴上的映射，Segment Tree可以帮助我们解决这类区间问题。
首先我们的关心的是range，所以叶节点也是range，也就是说我们的叶节点是类似[1, 2], [2, 3]这种而不是之前有的题目我们会存的[1, 1]，[2, 2]。其次就是我们在每一个node上存什么，这里有多种思路。首先我们要知道的是每个区间有多长被cover了，记作coveredRange。但是我们不能直接存这个，比如我们插入了两次[1, 3]，之后又删除了[1, 3]一次，这时候[1, 3]仍然是被完全覆盖的，但是只存coveredRange的话我们是没法检测这种情况的。所以我们转而存当前区间被完全覆盖的次数，因为我们需要区间更新，所以我们采用lazy propagation的实现方式，具体查看上面的文章。更新的话按部就班，查询的话如果当前区间被完全覆盖了我们直接return对应的的range，否则递归查询左右两个子区间。这里我们仍然要用index compression来压缩输入x和y的范围，我们可以去重也可以不去重，不会影响结果。时间复杂度O(N log N)，空间复杂度O(N)，代码如下：

class Node
{
public:
int cnt;//# of times the range is fully covered
int start, end, mark;//lazy propagation
Node* left, *right;
Node(int s, int e)
{
cnt = 0;
mark = 0;
start = s;
end = e;
left = nullptr;
right = nullptr;
}
Node* getLeft()
{
if (start + 1 >= end)
return nullptr;
if (left)return left;
int mid = start + (end - start) / 2;
left = new Node(start, mid);
left->cnt = cnt;
return left;
}
Node* getRight()
{
if (start + 1 >= end)
return nullptr;
if (right)return right;
int mid = start + (end - start) / 2;
right = new Node(mid, end);
right->cnt = cnt;
return right;
}
void update(int s, int e, int val)
{
if (mark)propagate();
if (s <= start && e >= end)
{
if (start + 1 < end)
{
getLeft()->mark += val;
getRight()->mark += val;
}
cnt += val;
return;
}
else if (s >= end || e <= start)
return;
else
{
getLeft()->update(s, e, val);
getRight()->update(s, e, val);
cnt = min(getLeft()->cnt, getRight()->cnt);
}
}
int query(int s, int e, vector<int>& map)
{
if (mark)propagate();
if (start + 1 >= end && !cnt)return 0;
if (s <= start && e >= end && cnt)
return map[end] - map[start];
else if (s >= end || e <= start)
return 0;
else
return getLeft()->query(s, e, map) + getRight()->query(s, e, map);
}
private:
void propagate()
{
if (start + 1 < end)
{
getLeft()->mark += mark;
getRight()->mark += mark;
}
cnt += mark;
mark = 0;
}
};
class Solution {
public:
int rectangleArea(vector<vector<int>>& rectangles) {
if (rectangles.empty())return 0;
const int MOD = 1000000007;
vector<vector<int>> events;
vector<int> xs;
for (const auto& rectangle : rectangles)
{
int x1 = rectangle[0], x2 = rectangle[2], y1 = rectangle[1], y2 = rectangle[3];
events.push_back({y1, 1, x1, x2});
events.push_back({ y2, -1, x1, x2 });
xs.push_back(x1);
xs.push_back(x2);
}
auto comp = [](const vector<int>& lhs, const vector<int>& rhs)
{
return lhs[0] == rhs[0] ? lhs[1] > rhs[1]: lhs[0] < rhs[0];
};
sort(events.begin(), events.end(), comp);
sort(xs.begin(), xs.end());
int len = events.size();
//compress input size by mapping it to [0, len - 1]
unordered_map<int, int> xMap;
for (int i = 0; i < len; ++i)xMap[xs[i]] = i;
long area = 0;
int last_y = events[0][0];
Node* root = new Node(0, len - 1);
root->update(xMap[events[0][2]], xMap[events[0][3]], events[0][1]);
for (int i = 1; i < len; ++i)
{
auto event = events[i];
int y = event[0];
area += static_cast<long>(y - last_y) * root->query(0, len - 1, xs);
area %= MOD;
root->update(xMap[event[2]], xMap[event[3]], event[1]);
last_y = y;
}
return area;
}
};
view raw Rectangle Area II_st_2.cpp hosted with ❤ by GitHub


官方给出的segment tree是另外一种存的方式，每个节点存了两个变量：

  • 当前区间被覆盖的长度，coveredRange
  • 输入区间能被分解成当前区间的次数cnt。比如[1, 4]，假设可以分解为[1, 3]和[3, 4]，这两个区间对应线段树里的两个node，我们把对应node的cnt数加1，而[1, 3]的子区间[1, 2]和[2, 3]我们不管。也就是说这里的cnt和上面的不太一样，不再具有父区间cnt的改变一定会影响到子区间的性质，反之亦然。这里每个node对应的cnt是相互独立的。
那么我们查询和更新的时候就可以根据这两个变量来进行操作。时间复杂度空间复杂度相同，代码如下：

class Node
{
public:
int cnt;//The total # of times that existing ranges can be splitted into this piece
int coveredRange;
int start, end;
Node* left, *right;
Node(int s, int e)
{
cnt = 0;
coveredRange = 0;
start = s;
end = e;
left = nullptr;
right = nullptr;
}
Node* getLeft()
{
if (start + 1 >= end)
return nullptr;
if (left)return left;
int mid = start + (end - start) / 2;
left = new Node(start, mid);
return left;
}
Node* getRight()
{
if (start + 1 >= end)
return nullptr;
if (right)return right;
int mid = start + (end - start) / 2;
right = new Node(mid, end);
return right;
}
void update(int s, int e, int val, vector<int>& map)
{
if (s <= start && e >= end)
cnt += val;
else if (s >= end || e <= start)
return;
else
{
getLeft()->update(s, e, val, map);
getRight()->update(s, e, val, map);
}
coveredRange = cnt ? map[end] - map[start] : (start + 1 >= end? 0 : getLeft()->coveredRange + getRight()->coveredRange);
}
};
class Solution {
public:
int rectangleArea(vector<vector<int>>& rectangles) {
if (rectangles.empty())return 0;
const int MOD = 1000000007;
vector<vector<int>> events;
vector<int> xs;
for (const auto& rectangle : rectangles)
{
int x1 = rectangle[0], x2 = rectangle[2], y1 = rectangle[1], y2 = rectangle[3];
events.push_back({y1, 1, x1, x2});
events.push_back({ y2, -1, x1, x2 });
xs.push_back(x1);
xs.push_back(x2);
}
auto comp = [](const vector<int>& lhs, const vector<int>& rhs)
{
return lhs[0] == rhs[0] ? lhs[1] > rhs[1]: lhs[0] < rhs[0];
};
sort(events.begin(), events.end(), comp);
sort(xs.begin(), xs.end());
int len = events.size();
//compress input size by mapping it to [0, len - 1]
unordered_map<int, int> xMap;
for (int i = 0; i < len; ++i)xMap[xs[i]] = i;
long area = 0;
int last_y = events[0][0];
Node* root = new Node(0, len - 1);
root->update(xMap[events[0][2]], xMap[events[0][3]], events[0][1], xs);
for (int i = 1; i < len; ++i)
{
auto event = events[i];
int y = event[0];
area += static_cast<long>(y - last_y) * root->coveredRange;
area %= MOD;
root->update(xMap[event[2]], xMap[event[3]], event[1], xs);
last_y = y;
}
return area;
}
};
view raw Rectangle Area II_st.cpp hosted with ❤ by GitHub

Posted by at
Labels: ,
Location: Newark, CA 94560, USA

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)