【多维分桶】N 个点中最多有多少点共线

字数统计: 2k字 | 阅读时长: 9分

2020-05-20

摘要: 分桶算法的经典题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章分桶法中，我们系统梳理了力扣上关于分桶法的题目。

本文我们解决一个多维分桶的经典计算几何问题：N 个点中最多有多少点共线，可以尝试以下两种分桶方法：

按照与固定点连成的线的斜率(long double)对点做哈希，用哈希值分桶。
用多层 treemap 实现多属性(横坐标和纵坐标)分桶。

首先解决最多的点数有多少，然后给出具体的点数最多的直线。

149. 直线上最多的点数

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

提示：

1 <= points.length <= 300
points[i].length == 2
-1e4 <= xi, yi <= 1e4
points 中的所有点 互不相同

示例 1:
输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
1
2
3
4
5
6
7
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4
示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
1
2
3
4
5
6
7
8
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

算法1 : 哈希分桶

枚举所有点，当枚举到点 i 时，枚举所有其它的点 j。

用 unordered_map 记录不同的点的个数，这里的相同指的是到点 i 的斜率相同。如果 j1 到 i 的斜率与 j2 到 i 的斜率相同，则 j1, j2 相同，在 unordered_map 中属于同一个键。

斜率的表示如果用 double 或者 long double 会有精度的问题，用 pair<int, int> 比较保险。对两个点求斜率，返回的是一个数对，它是一个向量。

返回的数对应该是没有公约数的，这里用到了辗转相除法。

对斜率做哈希即是对返回的数 pair<int, int> slope 对做哈希：

1	hash(slope) := ((ll)hash<int>()(slope.first) * 10007 + hash<int>()(slope.second)) % MOD;

自定义哈希函数相关的写法问题，参考 STL无序关联容器自定义哈希函数。

每枚举完一个点 i，都可以求出一个出现最多的点，将这个最多的个数如果比当前答案大，就更新答案。

对于后枚举的点 i，如果其余的点 j 中出现最多的点里有在 i 之前的，例如点 k ($k < i$)，则该答案在枚举到 k 时候就更新到答案里了，这里也就不用枚举点 k 了，因此枚举 j 时所有小于 i 的点就不用考虑了。

需要特判的边界条件：

重合的点
两点连线是竖线

代码(C++)

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        if(points.empty()) return 0;
        int n = points.size();
        if(n == 1 || n == 2) return n;
        int ans = 1;
        for(int i = 0; i < n; ++i)
        {
            Point origin(points[i][0], points[i][1]);
            int result = 0;
            int duplicates = 1;
            unordered_map<PPP, int, MyHash, MyCmp> mapping;
            mapping.insert({{origin, origin}, 1});
            for(int j = i + 1; j < n; ++j)
            {
                Point cur(points[j][0], points[j][1]);
                if(cur == origin)
                    ++duplicates;
            }
            for(int j = i + 1; j < n; ++j)
            {
                Point cur(points[j][0], points[j][1]);
                if(cur == origin)
                    continue;
                PPP cur_pair({origin, cur});
                ++mapping[cur_pair];
                result = max(result, mapping[cur_pair]);
            }
            result += duplicates;
            ans = max(ans, result);
        }
        return ans;
    }

private:
    using PII = pair<int, int>;
    class Point
    {
    public:
        Point(int x, int y): x(x), y(y) {}

        PII get_slope(const Point& origin) const
        {
            int dx = x - origin.x, dy = y - origin.y;
            if(dx == 0 && dy == 0) return PII({0, 0});
            if(dx == 0) return PII({0, 1});
            if(dy == 0) return PII({1, 0});
            if(dy < 0)
            {
                dy = -dy;
                dx = -dx;
            }
            int dx_sign = 1;
            if(dx < 0)
            {
                dx = -dx;
                dx_sign = -1;
            }
            int gcd = _gcd(dx, dy);
            dx /= gcd;
            dx *= dx_sign;
            dy /= gcd;
            return PII({dx, dy});
        }

        int get_x() const {return x;}
        int get_y() const {return y;}

        bool operator ==(const Point& point) const
        {
            return point.get_x() == x && point.get_y() == y;
        }

        bool operator !=(const Point& point) const
        {
            return !(*this == point);
        }

    private:
        int x, y;
        int _gcd(int x, int y) const
        {
            return x == 0 ? y : _gcd(y % x, x);
        }
    };

    using PPP = pair<Point, Point>;

    class MyHash
    {
    public:
        int operator()(const PPP& point_pair) const
        {
            PII slope = point_pair.second.get_slope(point_pair.first);
            return ((ll)hash<int>()(slope.first) * 10007 + hash<int>()(slope.second)) % MOD;
        }
        const int MOD = 1e9 + 7;
        using ll = long long;
    };

    class MyCmp
    {
    public:
        bool operator()(const PPP& point_pair1, const PPP& point_pair2) const
        {
            PII slope1 = point_pair1.second.get_slope(point_pair1.first);
            PII slope2 = point_pair2.second.get_slope(point_pair2.first);
            return slope1 == slope2;
        }
    };
};

算法2 : 多维 TreeMap 分桶

将方向向量的横坐标和纵坐标分别视为属性。用两层 treemap 分别维护横坐标和纵坐标的分桶。

设计多层 TreeMap 如下：

1	map<int, map<int, int>> mapping;

其中 mapping[i][j] 表示经过 points[i] 的直线中方向向量除以最大公约数后为 (i, j) 的点的个数, i >= 0。

代码 (C++)

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if(n == 1)
            return 1;
        int max_cnt = 0;
        for(int i = 0; i < n - 1; ++i)
        {
            // 经过 points[i] 的直线
            // mapping[i][j] := 方向向量除以最大公约数后为 (i, j) 的点数, i >= 0
            map<int, map<int, int>> mapping;
            int duplicate = 1;
            for(int j = i + 1; j < n; ++j)
            {
                int a = points[i][0] - points[j][0];
                int b = points[i][1] - points[j][1];
                if(a == 0 && b == 0)
                {
                    ++duplicate;
                    continue;
                }
                if(a < 0)
                {
                    a = -a;
                    b = -b;
                }
                if(a != 0 && b != 0)
                {
                    int gcd_ = gcd<int>(abs(a), abs(b));
                    a /= gcd_;
                    b /= gcd_;
                }
                else if(b != 0)
                    b = INT_MAX / 2;
                else if(a != 0)
                    a = INT_MAX / 2;
                ++mapping[a][b];
            }
            max_cnt = max(max_cnt, duplicate);
            for(auto a: mapping)
                for(auto b: a.second)
                    max_cnt = max(max_cnt, b.second + duplicate);
        }
        return max_cnt;
    }
};

$3 面试题 16.14. 最佳直线

给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。

设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，若有多条直线穿过了相同数量的点，则选择S[0]值较小的直线返回，S[0]相同则选择S[1]值较小的直线返回。

提示：

1 2	2 <= len(Points) <= 300 len(Points[i]) = 2

示例：
输入： [[0,0],[1,1],[1,0],[2,0]]
输出： [0,2]
解释：所求直线穿过的3个点的编号为[0,2,3]

算法：多层 TreeMap

将方向向量的横坐标和纵坐标分别视为属性。用两层 treemap 分别维护横坐标和纵坐标的分桶。

设计多层 TreeMap 如下：

1	map<int, map<int, set<int>>> mapping;

其中 mapping[i][j] 表示经过 points[i] 的直线中方向向量除以最大公约数后为 (i, j) 的点的集合, i >= 0。

代码 (C++)

class Solution {
public:
    vector<int> bestLine(vector<vector<int>>& points) {
        int n = points.size();
        int max_cnt = 0;
        int p1 = -1, p2 = -1;
        for(int i = 0; i < n - 1; ++i)
        {
            // 经过 points[i] 的直线
            // mapping[i][j] := 方向向量除以最大公约数后为 (i, j) 的点的集合, i >= 0
            map<int, map<int, set<int>>> mapping;
            vector<int> duplicate(1, i);
            for(int j = i + 1; j < n; ++j)
            {
                int a = points[i][0] - points[j][0];
                int b = points[i][1] - points[j][1];
                if(a == 0 && b == 0)
                {
                    duplicate.push_back(j);
                    continue;
                }
                if(a < 0)
                {
                    a = -a;
                    b = -b;
                }
                if(a != 0 && b != 0)
                {
                    int gcd_ = gcd<int>(abs(a), abs(b));
                    a /= gcd_;
                    b /= gcd_;
                }
                else if(b != 0)
                    b = INT_MAX / 2;
                else if(a != 0)
                    a = INT_MAX / 2;
                mapping[a][b].insert(j);
            }
            for(auto a: mapping)
                for(auto b: a.second)
                {
                    set<int> &setting = b.second;
                    for(int i: duplicate)
                        setting.insert(i);
                    if((int)setting.size() > max_cnt)
                    {
                        max_cnt = b.second.size();
                        p1 = *setting.begin();
                        p2 = *++(setting.begin());
                    }
                    else if((int)setting.size() == max_cnt)
                    {
                        if(*setting.begin() < p1)
                        {
                            p1 = *setting.begin();
                            p2 = *++(setting.begin());
                        }
                        else if(*setting.begin() == p1 && *++setting.begin() < p2)
                        {
                            p2 = *++(setting.begin());
                        }
                    }
                }
        }
        return {p1, p2};
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

数几何

【多维分桶】N 个点中最多有多少点共线

149. 直线上最多的点数

算法1 : 哈希分桶

代码(C++)

算法2 : 多维 TreeMap 分桶

代码 (C++)

$3 面试题 16.14. 最佳直线

算法：多层 TreeMap

代码 (C++)