计算数组中共线的三元组数

Question

我被问到这个采访问题(C++,algos)并且不知道如何解决它.

给定一个数组说Arr [N]包含N个不同点的笛卡尔坐标,计算三元组的数量(Arr [P],Arr [Q],Arr [R]),使得P <Q <R <N并且得到点Arr [ P],Arr [Q],Arr [R]共线(即位于同一直线上).

有任何想法吗？我可以使用什么算法？

Answer 1

以下内容可能未经过优化,但其复杂性是您的面试官要求的.

首先为每对点创建一个(a,b,c)值列表(N²复杂度) - >(a,b,c)代表直线a*x + b*y + c的笛卡尔方程给定两个点及其坐标(xa,ya)和(xb,yb),计算(a,b,c)很简单.你可以找到解决方案

ya=alpha*xa+beta  
yb=alpha*xb+beta

(if (xb-xa) != 0)
alpha = (yb-ya)/(xb-xa)
beta = ya - alpha*xa
a = alpha
b = -1
c = beta

或者

xa = gamma*ya+delta
xb = gamma*yb+delta
(you get the point)

然后可以以更一般的形式重写可解的方程组

a*x+b*y+c = 0

然后对列表进行排序(N²log(N²)复杂度因此N²log(N)复杂度).

迭代列表的元素.如果两个连续元素相等,则对应点是共线的.N²的复杂性.

您可能希望添加最后一个操作来过滤重复的结果,但您应该很好,复杂性.

编辑:我在编码时更新了一点算法,使其更简单和最优.在这里.

#include <map>
#include <set>
#include <vector>
#include <iostream>

struct StraightLine
{
    double a,b,c;
    StraightLine() : a(0.),b(0.),c(0.){}
    bool isValid() { return a!=0. || b!= 0.; }
    bool operator<(StraightLine const& other) const
    {
        if( a < other.a ) return true;
        if( a > other.a ) return false;
        if( b < other.b ) return true;
        if( b > other.b ) return false;
        if( c < other.c ) return true;
        return false;
    }
};

struct Point { 
    double x, y; 
    Point() : x(0.), y(0.){}
    Point(double p_x, double p_y) : x(p_x), y(p_y){}
};

StraightLine computeLine(Point const& p1, Point const& p2)
{
    StraightLine line;
    if( p2.x-p1.x != 0.)
    {
        line.b = -1;
        line.a = (p2.y - p1.y)/(p2.x - p1.x);
    }
    else if( p2.y - p1.y != 0. )
    {
        line.a = -1;
        line.b = (p2.x-p1.x)/(p2.y-p1.y);
    }
    line.c = - line.a * p1.x - line.b * p1.y;
    return line;
}

int main()
{
    std::vector<Point> points(9);
    for( int i = 0 ; i < 3 ; ++i )
    {
        for( int j = 0; j < 3 ; ++j )
        {
            points[i*3+j] = Point((double)i, (double)j);
        }
    }


    size_t nbPoints = points.size();
    typedef std::set<size_t> CollinearPoints;
    typedef std::map<StraightLine, CollinearPoints> Result;
    Result result;

    for( int i = 0 ; i < nbPoints ; ++i )
    {
        for( int j = i + 1 ; j < nbPoints ; ++j )
        {
            StraightLine line = computeLine(points[i], points[j]);
            if( line.isValid() )
            {
                result[line].insert(i);
                result[line].insert(j);
            }
        }
    }

    for( Result::iterator currentLine = result.begin() ; currentLine != result.end(); ++currentLine )
    {
        if( currentLine->second.size() <= 2 )
        {
            continue;
        }
        std::cout << "Line";
        for( CollinearPoints::iterator currentPoint = currentLine->second.begin() ; currentPoint != currentLine->second.end() ; ++currentPoint )
        {
            std::cout << " ( " << points[*currentPoint].x << ", " << points[*currentPoint].y << ")";
        }
        std::cout << std::endl;
    }
    return 0;
}