Объяснение и сложность для видимых точек в codefight - PullRequest
Новая
       63

Объяснение и сложность для видимых точек в codefight

0 голосов
/ 28 января 2020

Я сталкивался с этим вопросом о кодовом бое / кодовом сигнале. Учитывая массив точек на плоскости, найдите максимальное количество точек, видимых с начала координат с углом обзора 45 градусов. 

int visiblePoints(std::vector<std::vector<int>> points) {


const double pi=M_PI,pi_45=M_PI_4,pi_360=M_PI*2.0;
const double epsilon=1e-10;
int n=points.size(),result=0;
vector<double> angles(n);
for(int i=0;i<n;i++){
    double angle=atan2(points[i][1],points[i][0]);
    angles[i]=angle;
    if(angle<pi_45-pi){
        angles.push_back(angle+pi_360);
    }
}
sort(angles.begin(),angles.end());
//std::sort(angles.begin(), angles.end());
for(auto it=angles.begin();it!=angles.begin()+n;++it){
    auto bound=upper_bound(it,angles.end(),*it+(pi_45+epsilon));
    int curr=distance(it,bound);
    if(curr>result){
        result=curr;
    }
}
return result;
/*
for (auto it = angles.begin(), e = angles.begin() + n; it != e; ++it) {
    auto bound = std::upper_bound(it, angles.end(), *it + (pi_over_4 + epsilon));
    int cur = std::distance(it, bound);
    if (cur > result)
        result = cur;
}
return result;
*/

Так что код в порядке, я могу понять, что здесь происходит. Я просто хотел проверить, является ли сложность времени O (NlogN). Первый для l oop принимает O (N) .points - это массив из нескольких точек в 2D. Например, points = [[1,1], [3,1], .....]. Тогда мы имеем сортировка Я предполагаю, что сортировка занимает O (N * logN). Конечно, быстрая сортировка в худшем случае занимает O (N ^ 2), но сейчас я проигнорирую этот факт. И тогда последний l oop снова равен O (N). Кроме того, сложность пространства в этом сценарии будет O (1) или O (N) (из-за сортировки). Спасибо

...