1. 題目

給定一個二維平面及平面上的 N 個點列表Points，其中第i個點的坐標為Points[i]=[Xi,Yi]。
請找出一條直線，其通過的點的數目最多。

設穿過最多點的直線所穿過的全部點編號從小到大排序的列表為S，你僅需返回[S[0],S[1]]作為答案
若有多條直線穿過了相同數量的點，則選擇S[0]值較小的直線返回，S[0]相同則選擇S[1]值較小的直線返回。

示例： 輸入： [[0,0],[1,1],[1,0],[2,0]] 輸出： [0,2] 解釋： 所求直線穿過的3個點的編號為[0,2,3]提示： 2 <= len(Points) <= 300 len(Points[i]) = 2

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/best-line-lcci
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 暴力法，固定一個點，遍歷所有剩余的
• 采用嵌套的哈希map，第一層key存儲斜率，第二層key存儲截距，value為點的set集合（存儲下標）
• 斜率不存在，單獨再開一個哈希表，key為與 x 軸的截距，value為點集合
• 遍歷所有集合找最多的
• 對相等長度的點集合排序，取出題目要求的最小的下標的
• 時間復雜度 $O(n^2)$

class Solution { public:vector<int> bestLine(vector<vector<int>>& points) {int i, j, g, dx, dy, maxCount = 0, n = points.size();double k, b;unordered_map<double,unordered_map<double,set<int>>> m;//k,b,pointsunordered_map<double,set<int>> v;//x軸截距，斜率不存在時的集合vector<set<int>> ans;for(i = 0; i < n-1; ++i){for(j = i+1; j < n; ++j){dx = points[j][0]-points[i][0];dy = points[j][1]-points[i][1];if(dx==0)//斜率不存在{if(v[double(points[i][0])].empty())v[double(points[i][0])].insert(i);v[double(points[i][0])].insert(j);}else{k = double(dy)/dx;b = double(points[i][1])-points[i][0]*k;if(m[k][b].empty())m[k][b].insert(i);m[k][b].insert(j);}}}for(auto& mi : m){for(auto& mii : mi.second){if(mii.second.size() > maxCount){maxCount = mii.second.size();ans.clear();ans.push_back(mii.second);}else if(mii.second.size() == maxCount)ans.push_back(mii.second);}}for(auto& vi : v){if(vi.second.size() > maxCount){maxCount = vi.second.size();ans.clear();ans.push_back(vi.second);}else if(vi.second.size() == maxCount)ans.push_back(vi.second);}sort(ans.begin(),ans.end(),[&](auto a, auto b){auto it1 = a.begin(), it2 = b.begin();if(*it1 == *it2)return *(++it1) < *(++it2);return *it1 < *it2;});auto it = ans[0].begin();return {*it,*(++it)};} };

660 ms 117.7 MB

總結

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 16.14. 最佳直线（哈希map+set）的全部內容，希望文章能夠幫你解決所遇到的問題。

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