段的起点和终点以 vector 的起点和终点给出。点列表以 vector 点给出。任务是找到包含每个点的线段数。
在我的解决方案中,起点,终点和点的每个元素分别被赋予了标签l,p和r,并存储在 vector 对中。然后,对 vector 首先按第一个元素排序,然后按第二个元素排序。最后,我遍历对 vector ,如果是起点,则增加变量的覆盖率;如果是终点,则减少变量的覆盖率;然后将其赋值给答案。
该算法似乎是正确的,但时间复杂度为O(nlog(n)),但超过了时间限制。代码的哪一部分慢?
代码:
vector<int> fast_count_segments(vector<int>& starts, vector<int>& ends, vector<int>& points) {
vector<int> cnt(points.size());
const int left_label = 1, point_label = 2, right_label = 3;
std::map<int, std::set<int>> orig_point_map;
vector<pair<int,int>> pairs(2*starts.size()+points.size());
int k = 0;
for (auto& i : starts)
{
pairs[k++] = std::make_pair(i, left_label);
}
for (auto& i : ends)
{
pairs[k++] = std::make_pair(i, right_label);
}
for (auto i = 0;i < points.size();i++)
{
int point = points[i];
pairs[k++] = std::make_pair(point, point_label);
orig_point_map[point].emplace(i);
}
std::sort(pairs.begin(), pairs.end());
int coverage = 0;
for (auto& x : pairs) {
if (x.second == 1) {
coverage++;
}
else if (x.second == 3) {
coverage--;
}
else {
std::set<int> indices = orig_point_map[x.first];
for(auto i : indices) {
cnt[i] = coverage;
}
}
}
return cnt;
}
最佳答案
尽管复杂度很高,但是您会创建很多副本,而这些副本可以避免。
您可以使用修改后的版本:
std::vector<int> fast_count_segments(std::vector<int> starts,
std::vector<int> ends,
const std::vector<int>& points) {
std::vector<int> cnt(points.size());
std::vector<std::pair<int, int>> pairs(points.size());
for (auto i = 0u; i != points.size(); ++i) {
pairs[i] = std::make_pair(points[i], i);
}
std::sort(starts.begin(), starts.end());
std::sort(ends.begin(), ends.end());
std::sort(pairs.begin(), pairs.end());
int coverage = 0;
auto it_start = starts.begin();
auto it_end = ends.begin();
for (auto& x : pairs) {
while (it_start != starts.end() && *it_start <= x.first) {
++it_start;
++coverage;
}
while (it_end != ends.end() && *it_end < x.first) {
++it_end;
--coverage;
}
cnt[x.second] = coverage;
}
return cnt;
}