这是编程面试基础
一书中的一段话:
Let P be a set of n points in the plane. Each point has integer coordinates. Design an efficient algorithm for computing a line that contains the maximum number of points in P.
解决方案部分是这样说的:
Every pair of distinct points defines a line. We can use a hash table
H to map lines to the set of points in P that lie on them.
下面是行
的散列函数:
// Hash function for Line.
struct HashLine {
size_t operator()(const Line& l) const {
return hash <int >()(l.slope.first) ^ hash <int >()(l.slope.second) ^ hash <int >()(l.intercept.first) ^ hash <int >()(l.intercept.second);
}
这里是斜率和截距的声明:
pair <int, int> get_canonical_fractional(int a, int b) {
int gcd = GCD(abs(a), abs(b));
a /= gcd, b /= gcd;
return b < 0 ? make_pair(-a, -b) : make_pair(a, b);
}
// Line function of two points , a and b, and the equation is
// y = x(b.y - a.y) / (b.x - a.x) + (b.x * a.y - a.x * b.y) / (b.x - a.x).
struct Line {
Line(const Point& a, const Point& b)
: slope(a.x != b.x ? get_canonical_fractional(b.y - a.y, b.x - a.x) : make_pair(1, 0))
, intercept(a.x != b.x ? get_canonical_fractional(b.x * a.y - a.x * b.y, b.x - a.x) : make_pair(a.x, 1))
{}
...
// Store the numerator and denominator pair of slope unless the line is
// parallel to y-axis that we store 1/0.
pair <int, int> slope;
// Store the numerator and denominator pair of the y-intercept unless
// the line is parallel to y-axis that we store the x-intercept.
pair <int, int> intercept;
};
但是我们怎么知道如果斜率和截距对是唯一的,那么它们的异或仍然是唯一的?
最佳答案
我们可以试试下面的简单算法:
- 创建一个散列映射,键为一条线的
(slope, intercept)
对,值为具有相同斜率截距的线的数量。 - 对于所有点对(
O(n^2)
对)计算(slope, intercept)
值并递增 hashmap 中的相应键(在最坏的情况,它会消耗O(n^2)
内存,但如果有很多共线点,那么平均空间复杂度应该很低。 - 输出行,即 hashmap 中计数最高的
(slope, intercept)
(为此,您需要遍历 hasmap,在最坏的情况下,该 hasmap 将包含O( n^2)
个条目)。
关于algorithm - "find the line that contains the maximum number of points in P"的哈希函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42337839/