提交效率:192 ms ,55%
这一题,出现了 javascript 精度问题。最后的案例 [[0,0],[94911151,94911150],[94911152,94911151]] 是没法通过的。会将会两个点计算为同一个斜率的,造成结果的不对。
94911150 / 94911151 = 0.9999999894638303 == 94911151 / 94911152
var maxPoints = function(points) { if(points.length<2 ) return points.length; var result = {"ins":0}; var max = 0; for(var j = 0 ; j < points.length; j++){ result = {"ins":0},base = 1,onthis = false; for(var i = 0, temp; i< points.length; i++){ if(points[i].x == points[j].x){ // 每多一个同点,所有点数加1 if(points[i].y == points[j].y){ for(var key in result){ result[key]++; } max = onthis? max+1:max; base++; }else{ result["ins"]++; } max = result["ins"] > max ? result["ins"] : max; continue; } temp = (points[i].y - points[j].y)/(points[i].x - points[j].x); result[temp] ? (result[temp]++):(result[temp] = base); result[temp] > max ? ( max = result[temp] ,onthis = true) : null; } } return max; };参考排名第一的方法,使用其它方式表示斜率:
var maxPoints = function(points) { let size = points.length; if (size < 2) return size; const gcd = (a, b) => { if (b === 0) return a; return gcd(b, a%b); } let res = 0; for (let i = 0; i < size; ++i) { let hash = new Map(); let horizontal = 0, vertical = 0, localMax = 0, overlap = 1; for (let j = i + 1; j < size; ++j) { let a = points[i], b = points[j]; if (a.x === b.x && a.y === b.y) ++overlap; else if (a.x === b.x) ++vertical; else if (a.y === b.y) ++horizontal; else { let dx = a.x - b.x; let dy = a.y - b.y; let d = gcd(dx, dy); dx = Math.floor(dx / d); dy = Math.floor(dy / d); let pair = "" + dx + "," + dy; let curPoints = hash.has(pair) ? hash.get(pair) + 1 : 1; hash.set(pair, curPoints); localMax = Math.max(localMax, curPoints); } } res = Math.max(res, overlap + Math.max(localMax, Math.max(vertical, horizontal))); } return res; };