Max Points on a Line

原題鏈接Max Points on a Line

給出2D平面中的n個坐標點，計算最多有多少個點在一條直線上

一條直線可以用斜率表示，即如果已知(x1,y1)，(x2,y2)(x1,y1)，(x2,y2)，那么斜率為(y2?y1)/(x2?x1)(y2?y1)/(x2?x1) ，所以固定一個點，然后遍歷其他點，將不同的斜率到個數的映射記錄在map中，然后求最大的

思路是這樣，但是由于浮點數計算有誤差，導致斜率的計算不是準確的，所以不能直接記錄斜率。因為斜率是由Δy/ΔxΔy/Δx計算得到的，那么可以采用<Δx,Δy><Δx,Δy><script type="math/tex" id="MathJax-Element-4"><\Delta x, \Delta y></script>到個數的映射，不過需要將Δx，ΔyΔx，Δy化為最簡的形式，這樣，就可以將<Δx,Δy><Δx,Δy><script type="math/tex" id="MathJax-Element-6"><\Delta x, \Delta y></script>這個數值對相等看成是斜率相等

化為最簡的方法是找到兩個數的最大公約數，使用輾轉相除法，計算步驟是

• 用第一個數除以第二個數得到余數
• 如果余數為0，則第二個數就是最大公約數，返回
• 否則，用第二個數除以余數，回到步驟1(即將第二個數作為新的第一個數，將余數作為新的第二個數)

另外需要注意的一點是坐標點可能存在重合的情況

代碼如下

/*** Definition for a point.* struct Point {* int x;* int y;* Point() : x(0), y(0) {}* Point(int a, int b) : x(a), y(b) {}* };*/ class Solution { public:int maxPoints(vector<Point>& points) {int count = 0;for(int i = 0; i < points.size(); ++i){/* 固定points[i]，遍歷其他點，記錄不同斜率個數，找最大的 */std::map<std::pair<int, int>, int> m;int cnt = 0;int samePointCnt = 0;for(int j = i + 1; j < points.size(); ++j){/* 記錄重合點 */if(points[i].x == points[j].x && points[i].y == points[j].y)++samePointCnt;else{int xDiff = points[i].x - points[j].x;int yDiff = points[i].y - points[j].y;/* 計算最大公約數 */int g = gcd(xDiff, yDiff);xDiff /= g;yDiff /= g;/* 添加到map中 */cnt = std::max(cnt, ++m[std::make_pair(xDiff, yDiff)]);}}count = std::max(count, cnt + samePointCnt + 1);}return count;} private:int gcd(int a, int b){if(b == 0)return a;elsereturn gcd(b, a % b);} };

這里之所以用map而不用unordered_map是因為std::pair沒有hash函數，所以如果要使用后者，就需要自己實現hash函數

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----平面上n个点，计算最多有多少个点在一条直线上的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。