计算共线数组中的三元组数 [英] Count Number of Triples in an array that are collinear

问题描述

有人问我这个面试问题（C ++，算法），却不知道如何解决。

I was asked this Interview Question (C++,algos)and had no idea how to solve it.

给出一个数组，说Arr [N]包含笛卡尔坐标N个不同的点计数三元组的数目（Arr [P]，Arr [Q]，Arr [R]），使得P ＜0。 Q ＜ R ＜ N和点Arr [P]，Arr [Q]，Arr [R]是共线的（即位于同一条直线上）。

Given an array say Arr[N] containing Cartesian coordinates of N distinct points count the number of triples (Arr[P], Arr[Q], Arr[R]) such that P < Q < R < N and the points Arr[P], Arr[Q], Arr[R] are collinear (i.e lie on the same straight line).

有什么想法吗？我可以为此使用哪种算法？

Any ideas? What algorithm can I use for this?

推荐答案

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

The following is probably not optimized, but its complexity is the one your interviewer requested.

首先为每个点（N²复杂度）创建一个（a，b，c）值列表
->（a，b，c ）代表直线的笛卡尔方程a * x + b * y + c = 0
给定两个点及其坐标（xa，ya）和（xb，yb），计算（a，b，c ）很简单。
您可以找到

First create a list of (a,b,c) values for each couple of points (N² complexity) --> (a,b,c) stands for the cartesian equation of a straight line a*x+b*y+c=0 Given two points and their coordinates (xa, ya) and (xb, yb), computing (a,b,c) is simple. Either you can find a solution to

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)

然后可以用更通用的形式重写可解方程组

The solvable set of equations can then be rewritten in the more general form

a*x+b*y+c = 0

然后对列表排序（N²log（N²）复杂度，因此N²log（N）复杂度）。

Then sort the list (N² log(N²) complexity therefore N²log(N) complexity).

迭代列表的元素。如果两个顺序元素相等，则对应的点是共线的。 N²复杂度。

Iterate over elements of the list. If two sequential elements are equal, corresponding points are collinear. N² complexity.

您可能想添加最后一个操作以过滤重复的结果，但是在复杂度方面应该没问题。

You might want to add a last operation to filter duplicate results, but you should be fine, complexity-wise.

编辑：我在编码时对算法进行了一些更新，使其更简单，更优化。

EDIT : i updated a bit the algorithm while coding it to make it more simple and optimal. Here it goes.

#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;
}

这篇关于计算共线数组中的三元组数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！