149. Max Points on a Line

題目描述

Given an array of points where points[i] = [

$x_i$,

$y_i$] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

範例

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -10⁴ <=
  $x_i$,
  $y_i$ <= 10⁴
• All the points are unique.

解答

Python

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        ans = 0
        for i, (x1, y1) in enumerate(points):
            count = defaultdict(int)
            for x2, y2 in points[i+1:]:
                dx, dy = x1 - x2, y1 - y2
                if dy < 0 or (dy == 0 and dx < 0):
                    dx, dy = -dx, -dy
                g = gcd(dx, dy)
                slope = dx // g, dy // g
                count[slope] += 1
            ans = max(ans, max(count.values(), default=0))
        return ans + 1

Yen-Chi ChenSun, Jan 8, 2023

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        return max([max(Counter([(dx // gcd(dx, dy), dy // gcd(dx, dy)) for dx, dy in [(-Dx, -Dy) if Dy < 0 or (Dy == 0 and Dx < 0) else (Dx, Dy) for Dx, Dy in [(x1 - x2, y1 - y2) for x2, y2 in points[i+1:]]]]).values(), default=0) for i, (x1, y1) in enumerate(points)]) + 1

Yen-Chi ChenSun, Jan 8, 2023

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        res = 0

        for i, (x1, y1) in enumerate(points):
            same_point = 1
            cnt = defaultdict(int)
            for x2, y2 in points[i+1:]:
                if x1 == x2 and y1 == y2:
                    same_point += 1
                elif x1 == x2:
                    cnt[math.inf] += 1
                else:
                    slope = (y1 - y2) / (x1 - x2)
                    cnt[slope] += 1

            local_max = max(cnt.values(), default=0) + same_point
            res = max(res, local_max)

        return res

Ron ChenMon, Jan 9, 2023

Javascript

function maxPoints(points) {
  if (points.length < 3) return points.length;

  let max = 0;

  // 紀錄每兩個點的斜率
  for (let i = 0; i < points.length; i++) {
    const map = new Map();
    let localMax = 1;
    for (let j = i + 1; j < points.length; j++) {
      const [x1, y1] = points[i];
      const [x2, y2] = points[j];
      const slope = getSlope(x1, y1, x2, y2);

      map.set(slope, map.has(slope) ? map.get(slope) + 1 : 2);
      localMax = Math.max(localMax, map.get(slope));
    }

    max = Math.max(max, localMax);
  }

  return max;
}

function getSlope(x1, y1, x2, y2) {
  if (x1 === x2) return null;
  if (y1 === y2) return 0;
  return (y2 - y1) / (x2 - x1);
}

MarsgoatJul 6, 2023

Reference

回到題目列表