m*****y
发帖数: 120 | 1 Given n 2D dots in 2D space (like: (1, 3), (2, 5), (2, 6), etc.)
Find all the ones that are on the same line (straight line). | e*****e
发帖数: 1275 | 2 这题目和那个一大堆点，找出那根线上点最多的题目好像阿~~ | m*****y
发帖数: 120 | 3 What is that?
【在 e*****e 的大作中提到】
: 这题目和那个一大堆点，找出那根线上点最多的题目好像阿~~
| s*****g
发帖数: 5159 | 4 每一对点算斜率，斜率相同的比截距。
【在 m*****y 的大作中提到】
: Given n 2D dots in 2D space (like: (1, 3), (2, 5), (2, 6), etc.)
: Find all the ones that are on the same line (straight line).
| e***l
发帖数: 710 | | s******c
发帖数: 1920 | 6 任意取两点，计算斜率和截距，能得到一条直线，然后把其他落在这条直线上的点也打
印出来。用一个set保存unique的（斜率，截距），这样不会重复选取。特殊情况是斜
率为无穷大，没有截距。
=============================================
#include
#include
using namespace std;
#define N 5
class Line{ //y=a*x+b
public:
float a,b;
Line ():a(0),b(0){}
Line (int n1,int n2):a(n1),b(n2){}
bool operator<(const Line &right)const{
if (a==right.a)
return b
else return a
}
bool operator==(const Line &right)const{
return (!(*this
}
};
set myset;
void creatline(Line &line,int *p1,int *p2) {
line.a=(p1[1]-p2[1])/(p1[0]-p2[0]);
line.b=p1[1]-(line.a)*p1[0];
}
int main() {
int points[N][2]={{0,0},{1,1},{2,2},{2,10},{2,6}};
set::iterator it;
int i,j,k;
Line l;
for (i=0; i
for (j=i+1; j
if(points[i][0]!=points[j][0]){
creatline(l,points[i],points[j]);
it = myset.find(l);
if (it!=myset.end()) //we've seen this line before
continue;
cout << "("<
cout << ", ("<
for (k=0; k
if (k!=i && k!=j && points[k][1]==((l.a)*points[k][0]+l.
b)) {
cout << ", ("<
}
}cout << endl;
myset.insert(l);
}
else {
l=Line(0xFFFFFFFF,points[i][0]); //now a is infinity, b
represent the x-axis value
it = myset.find(l);
if (it!=myset.end())
continue;
cout << "("<
cout << ", ("<
for (k=0; k
if (k!=i && k!=j && points[k][0]==points[i][0]) {
cout << ", ("<
}
}cout << endl;
myset.insert(l);
}
}
}
cout << myset.size() << " lines in total."<
} | D*****d
发帖数: 1307 | 7 这样的话， 复杂度有O(n^2)吧
一般情况下， 这种算法的面试题答案的复杂度重不重要？
正在找实习中。。。
【在 m*****y 的大作中提到】
: Given n 2D dots in 2D space (like: (1, 3), (2, 5), (2, 6), etc.)
: Find all the ones that are on the same line (straight line).
| p*****r
发帖数: 56 | 8 非常重要.
主要考的就是復雜度.
白板寫代碼只是看你熟不熟.
~
【在 D*****d 的大作中提到】
: 这样的话， 复杂度有O(n^2)吧
: 一般情况下， 这种算法的面试题答案的复杂度重不重要？
: 正在找实习中。。。
| d****2
发帖数: 12 | 9 The time complexity is O(n^3), not n^2. for each pair of points (n^2), you
have to check with the rest of the points (n). so total O(n^3). Don't know
whether there is any algo can do better than this though. | m*****y
发帖数: 120 | 10 I just got an idea with n*n*logn time complexity:
Pair wise get all slope and intersection to X axis. This is n*n, resulting
in n*n pairs.
Sort the n*n pairs to find the same ones (on same line), n*n*log(n*n) => n*n
*logn.
So the final complex is n*n*logn. | s******c
发帖数: 1920 | | m*****y
发帖数: 120 | 12 yes, sort is nlogn, and here n is actually n*n, so it is n*n*log(n*n) => n*n
*logn. | z**c
发帖数: 625 | 13 就对所有的边做一遍hashtable就完了。
for each edge (a和b是任意两点）:
if hashtable contains 的斜率和节距, 把 a 和 b 插到 hashtable
else 新插一个pair到hashtable
O(N^2)
【在 d****2 的大作中提到】
: The time complexity is O(n^3), not n^2. for each pair of points (n^2), you
: have to check with the rest of the points (n). so total O(n^3). Don't know
: whether there is any algo can do better than this though.
|
|
