149.直线上最多的点数

链接：149.直线上最多的点数
难度：Hard
标签：几何、数组、哈希表、数学
简介：给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

题解 1 - typescript

• 编辑时间：2021-06-24
• 执行用时：152ms
• 内存消耗：49.7MB
• 编程语言：typescript
• 解法介绍：储存下标进行判断数量。

function maxPoints(points: number[][]): number {
  const len = points.length;
  if (len === 1) return 1;
  const cacheKB: Record<string, Set<number>> = {};
  const cacheX: Record<string, Set<number>> = {};
  for (let i1 = 0; i1 < len; i1++) {
    const [x1, y1] = points[i1];
    for (let i2 = i1 + 1; i2 < len; i2++) {
      const [x2, y2] = points[i2];
      if (x1 === x2) {
        let set = cacheX[x1];
        if (!set) set = cacheX[x1] = new Set();
        set.add(i1);
        set.add(i2);
      } else {
        const k = (y1 - y2) / (x1 - x2);
        const b = y1 - k * x1;
        const str = `k=${k},b=${b}`;
        let set = cacheKB[str];
        if (!set) set = cacheKB[str] = new Set();
        set.add(i1);
        set.add(i2);
      }
    }
  }
  return Math.max(
    ...Object.values(cacheKB).map(v => v.size),
    ...Object.values(cacheX).map(v => v.size)
  );
}