我被问到这个采访问题（C ++，algos）并且不知道如何解决它。
给定一个数组说Arr [N]包含N个不同点的笛卡尔坐标，计算三元组的数量（Arr [P]，Arr [Q]，Arr [R]），使得P <Q <R <N并且得到点Arr [ P]，Arr [Q]，Arr [R]共线（即位于同一直线上）。
有任何想法吗？我可以使用什么算法？
以下内容可能未经过优化，但其复杂性是您的面试官要求的。
首先为每对点创建一个（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;
}
如果是2维点：如果（P，Q），（P，R）定义相同的斜率，则3点（P，Q，R）是共线的。
m = (p.x - q.x) / (p.y - q.y) ; slope
不知怎的，你需要检查所有可能的组合并检查，一个有效的算法是技巧，因为第一个天真是N *（N-1）*（N-2）......
不是3个循环，而是O（n³），预先计算由两个点Arr[P], Arr[Q]给出的所有线的斜率。那是O（n²）。然后比较这些斜率。
您可以在计算期间或之后通过其斜率进一步对线进行排序，即O（n log n）。之后，找到具有相同斜率的线是O（n）。
但是，当您想知道哪些点是共线时，您可能需要通过实施数据结构来为此付出代价。
我认为面试问题的关键不在于提供完美的算法，而在于识别和讨论一个想法中的问题。
编辑：
蛮力方法：
#include <iostream>
#include <vector>
struct Point { int x, y; };
bool collinear(Point P, Point Q, Point R)
{
// TODO: have to look up for math ... see icCube's answer
return false;
}
int main()
{
std::vector<Point> v;
Point a;
while (std::cin >> a.x >> a.y)
{
v.push_back(a);
}
int count = 0;
for (int p = 0; p < v.size(); ++p)
{
for (int q = p+1; q < v.size(); ++q)
{
for (int r = q+1; r < v.size(); ++r)
{
if (collinear(v[p], v[q], v[r])) ++count;
}
}
}
std::cout << count << '\n';
return 0;
}
对于共线三元组的计数，识别具有任意两个点的线，然后检查由任何其他两个点形成的新线是否可能是重合的或平行的，并且在计算共线三元组时需要注意。
要解决：
Map<Line, Set<Point2d>>收集一行上的所有点。以下问题的代码如下
import java.util.*;
public class CollinearTriplets {
public static void main(String[] args) {
Point2d A[] = new Point2d[8];
A[0] = new Point2d(0, 0);
A[1] = new Point2d(1, 1);
A[2] = new Point2d(2, 2);
A[3] = new Point2d(3, 3);
A[4] = new Point2d(3, 2);
A[5] = new Point2d(4, 2);
A[6] = new Point2d(5, 1);
A[7] = new Point2d(4, 4);
System.out.println(countCollinear(A));
}
public static int factorial(int n) {
int fact = 1;
for (int i = 1; i <= n; i++) {
fact = fact * i;
}
return fact;
}
private static int combinations(int n, int r) {
return factorial(n) / (factorial(n - r) * factorial(r));
}
private static long countCollinear(Point2d[] points) {
Map<Line, Set<Point2d>> lineToPoints = new HashMap<>();
long result = 0;
for (int i = 0; i < points.length; i++) {
for (int j = i + 1; j < points.length; j++) {
double slope = 0d, xIntercept, yIntercept; // Default slope paralell to y-axis
if (points[i].x == points[j].x) {
slope = Double.MAX_VALUE; // Horizontal slope parallel to x-axis
} else if (points[i].y != points[j].y) {
xIntercept = points[j].x - points[i].x;
yIntercept = points[j].y - points[i].y;
slope = yIntercept / xIntercept;
}
Line currLine = new Line(points[i], slope);
if (Objects.isNull(lineToPoints.get(currLine))) {
lineToPoints.put(currLine, new HashSet<>());
}
lineToPoints.get(currLine).add(points[i]);
lineToPoints.get(currLine).add(points[j]);
}
}
for (Line line : lineToPoints.keySet()) {
int size = lineToPoints.get(line).size();
if (size >= 3) {
result = result + combinations(size, 3);
}
}
return result;
}
/**
* Line which contains the starting point and slope so that you can identify exact line
* equals method is overridden to check whether any new line is coinciding or parallel
*/
static class Line {
Point2d point;
double slope;
public Line(Point2d point, double slope) {
this.point = point;
this.slope = slope;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Line)) return false;
Line line = (Line) o;
if (line.slope == this.slope)
return ((((double) (line.point.y - this.point.y)) / (line.point.x - this.point.x)) == this.slope);
return false;
}
@Override
public int hashCode() {
return Objects.hash(slope);
}
}
static class Point2d {
int x;
int y;
public Point2d(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Point2d)) return false;
Point2d point2d = (Point2d) o;
return x == point2d.x &&
y == point2d.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
}
上面的代码O(N^2)和空间复杂度的时间复杂度是O(N)
看到你可以在O（n ^ 2）时间内得到所有的点对和它们的斜率和y截距是微不足道的。所以输出是：
IndexB Slope Y-Intercept IndexA
当然，我们不会插入任何IndexA = IndexB的条目。
让我们将这个表编入索引（IndexB，Slope，Y），这将强制我们插入此表中为O（log（n））
在我们用新记录（B'，S'，Y'，A'）填写此表后，我们检查是否已经有一个元素，使得B'=现有表的A和B！= A'的新记录（意思是我们有一个独特的三元组）匹配斜率和Y轴截距（意味着共线）。如果是这种情况并且A <B <B'，则将计数增加1。
编辑：一个澄清的评论。我们需要确保首先将这个表“向后”填充，取出所有不满足A <B（<C）的对。这可以确保在我们开始测试它们的存在之前它们将存在于表中。
编辑：哇我的C ++生锈...花了一段时间。
#include <iostream>
#include <vector>
#include <set>
#include <stdlib.h>
#include <math.h>
using namespace std;
#define ADD_POINT(xparam,yparam) { point x; x.x = xparam; x.y = yparam; points.push_back(x); };
#define EPSILON .001
class line {
public:
double slope;
double y;
int a;
int b;
bool operator< (const line &other) const{
if(this->a < other.a)
return true;
else if(this->a==other.a){
if(this->slope-other.slope < -EPSILON)
return true;
else if(fabs(this->slope-other.slope) < EPSILON){
if(this->y-other.y < -EPSILON)
return true;
else
return false;
}else
return false;
}else
return false;
}
line(double slope, double y, int a, int b){
this->slope = slope;
this->y = y;
this->a = a;
this->b = b;
}
line(const line &other){
this->slope = other.slope;
this->y = other.y;
this->a = other.a;
this->b = other.b;
}
};
class point {
public:
double x;
double y;
};
int main(){
vector<point> points;
ADD_POINT(0,0);
ADD_POINT(7,28);
ADD_POINT(1,1);
ADD_POINT(2,3);
ADD_POINT(2,4);
ADD_POINT(3,5);
ADD_POINT(3,14);
ADD_POINT(5,21);
ADD_POINT(9,35);
multiset<line> lines;
for(unsigned int x=0;x<points.size();x++){
for(unsigned int y=0;y<points.size();y++){
if(x!=y){ // No lines with the same point
point a = points[x];
point b = points[y];
double slope = (a.y-b.y)/(a.x-b.x);
double yint;
yint = a.y-a.x*slope;
line newline(slope,yint,x,y);
lines.insert(newline);
}
}
}
for(multiset<line>::const_iterator p = lines.begin(); p != lines.end(); ++p){
//cout << "Line: " << p->a << " " << p->b << " " << p->slope << " " << p->y << endl;
line theline = *p;
line conj(theline.slope,theline.y,theline.b,-1);
multiset<line>::iterator it;
pair<multiset<line>::iterator,multiset<line>::iterator> ret;
ret = lines.equal_range(conj);
for(it = ret.first; it!=ret.second; ++it){
//cout << " Find: " << it->a << " " << it->b << " " << it->slope << " " << it->y << endl;
int a = theline.a;
int b = theline.b;
int c = it->b;
if(a < b && b < c){
cout << a << " " << b << " " << c << std::endl;
}
}
}
//cout << points[0].x << std::endl;
}
我有这个解决方案告诉你是否有一个更好的，
根据它们使用x轴或任何其他所需的轴（O（n * logn））对所有点进行排序。现在，如果经过排序列表并找到在正方向或负方向上具有相同斜率的点，则需要做的就是这一点（这可以在线性时间内完成，即O（n））。让我们说你得到一个案例的m点，然后用C（m，3）递增答案。
总时间取决于你实现C（m，3）的好坏程度
但渐近O（N logN）
编辑：在看到icCube的评论后，我意识到我们不能采取任何轴..所以对于上面定义的算法，将斜率计算点作为n个点之一（因此n次）应该是我最好的猜测。但它使算法N * N * Log（N）