本文主要是介绍149. 直线上最多的点数 没有通过---,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
149. 直线上最多的点数
难度困难132收藏分享切换为英文关注反馈
给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。
示例 1:
输入: [[1,1],[2,2],[3,3]] 输出: 3 解释: ^ | | o | o | o +-------------> 0 1 2 3 4
示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] 输出: 4 解释: ^ | | o | o o | o | o o +-------------------> 0 1 2 3 4 5 6
class Solution {
public:int maxPoints(vector<vector<int>>& points) {if(points.empty()){return 0;} unordered_map<long double, int> hash;int result = 1;for(int i =0; i< points.size() ; i++){int vertical = 1;int duplicate =0;for (int j =i+1 ; j<points.size();j++ ){if (points[i][0] == points[j][0]) {vertical ++;if (points[i][1] == points[j][1]) {duplicate++; } } }for (int j =i + 1; j<points.size(); j++){if(points[i][0] != points[j][0] ) {long double slope = (long double) (points[i][1] - points[j][1]) / (points[i][0] - points[j][0]);if(!hash.count(slope)) hash[slope] =2;else {hash[slope] ++;}result = max(result ,hash[slope] + duplicate);}}result = max(result,vertical); } return result;}
};
这篇关于149. 直线上最多的点数 没有通过---的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!