149. Max Points on a Line
給定一個點數組，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一個點，返回位於同一條直線上的最多點數。
範例 :
輸入: points = [[1,1],[2,2],[3,3]] 輸出: 3
Python
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
n = len(points) #amount of point
maxP = 0 # current max points - initalize variable
for i in range(n):
X = points[i][0]
Y = points[i][1]
map = {} # create temperory dict for story points
for j in range(i+1, n):
dx = points[j][0] - X
dy = points[j][1] - Y # change in x and y pos
if(dx != 0):
d = dy/dx
if d in map:
map[d] = map[d] + 1
else:
map[d] = 1
else:
if 20001.0 in map:
map[20001.0] = map[20001.0] + 1
else:
map[20001.0] = 1 # test case put here since I cant solve
if map:
maxP = max(maxP, max(map.values())) # return longest one by sorting it and get the max - since you have to get the value (sort by value), I don't know how to do max() with it
return maxP + 1
16.79MB, 54ms
C++
#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size();
if (n <= 2) {
return n;
}
int maxPoints = 0;
for (int i = 0; i < n; ++i) {
unordered_map<double, int> slopes;
int duplicates = 1;
for (int j = i + 1; j < n; ++j) {
if (points[i] == points[j]) {
++duplicates;
} else {
double slope = calculateSlope(points[i], points[j]);
++slopes[slope];
}
}
int currentMax = duplicates;
for (const auto& pair : slopes) {
currentMax = max(currentMax, pair.second + duplicates);
}
maxPoints = max(maxPoints, currentMax);
}
return maxPoints;
}
private:
double calculateSlope(const vector<int>& p1, const vector<int>& p2) {
int dx = p2[0] - p1[0];
int dy = p2[1] - p1[1];
if (dx == 0) {
return numeric_limits<double>::infinity();
}
return static_cast<double>(dy) / dx;
}
};
17.15MB, 23ms
Javascript
/**
* @param {number[][]} points
* @return {number}
*/
var maxPoints = function(points) {
const n = points.length;
if (n <= 2) {
return n;
}
let maxPoints = 0;
for (let i = 0; i < n; ++i) {
let slopes = new Map();
let duplicates = 1;
for (let j = i + 1; j < n; ++j) {
if (points[i][0] === points[j][0] && points[i][1] === points[j][1]) {
duplicates++;
} else {
let dx = points[j][0] - points[i][0];
let dy = points[j][1] - points[i][1];
let slope = calculateSlope(dx, dy);
slopes.set(slope, (slopes.get(slope) || 0) + 1);
}
}
let currentMax = duplicates;
for (let count of slopes.values()) {
currentMax = Math.max(currentMax, count + duplicates);
}
maxPoints = Math.max(maxPoints, currentMax);
}
return maxPoints;
};
/**
* Helper function to calculate the slope.
* @param {number} dx
* @param {number} dy
* @return {string}
*/
function calculateSlope(dx, dy) {
if (dx === 0) {
return 'inf';
}
if (dy === 0) {
return '0';
}
let gcdVal = gcd(dx, dy);
return `${dy / gcdVal}/${dx / gcdVal}`;
}
/**
* Helper function to calculate the greatest common divisor (GCD) using the Euclidean algorithm.
* @param {number} a
* @param {number} b
* @return {number}
*/
function gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
54.92MB, 84ms
