LeetCode 149. 直线上最多的点数

Categories:

题目描述
思路分析
1. 解法一：枚举基准点 + 斜率哈希（推荐）
相似题目

题目描述

✅ 149. 直线上最多的点数

思路分析

解法一：枚举基准点 + 斜率哈希（推荐）

核心思路：

以每个点为基准，统计与其构成同一直线的点数。

用最大公约数规范化斜率 (dy, dx)，避免精度问题。

处理重合点数量并合并到结果中。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示点数量。

空间复杂度：O(n)，用于记录斜率计数。

import java.util.*;

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) {
            return n;
        }

        int ans = 1;
        // 枚举基准点
        for (int i = 0; i < n; i++) {
            Map<String, Integer> map = new HashMap<>();
            int same = 0;
            int max = 0;

            // 统计与基准点的斜率
            for (int j = i + 1; j < n; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];

                if (dx == 0 && dy == 0) {
                    same++;
                    continue;
                }

                int g = gcd(Math.abs(dx), Math.abs(dy));
                dx /= g;
                dy /= g;

                // 统一符号
                if (dx < 0) {
                    dx = -dx;
                    dy = -dy;
                } else if (dx == 0) {
                    dy = 1;
                } else if (dy == 0) {
                    dx = 1;
                }

                String key = dy + "/" + dx;
                int cnt = map.getOrDefault(key, 0) + 1;
                map.put(key, cnt);
                max = Math.max(max, cnt);
            }

            ans = Math.max(ans, max + same + 1);
        }

        return ans;
    }

    private int gcd(int a, int b) {
        // 辗转相除法
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

import "fmt"

func maxPoints(points [][]int) int {
	n := len(points)
	if n <= 2 {
		return n
	}

	ans := 1
	// 枚举基准点
	for i := 0; i < n; i++ {
		m := make(map[string]int)
		same := 0
		maxCnt := 0

		// 统计与基准点的斜率
		for j := i + 1; j < n; j++ {
			dx := points[j][0] - points[i][0]
			dy := points[j][1] - points[i][1]

			if dx == 0 && dy == 0 {
				same++
				continue
			}

			g := gcd(abs(dx), abs(dy))
			dx /= g
			dy /= g

			// 统一符号
			if dx < 0 {
				dx = -dx
				dy = -dy
			} else if dx == 0 {
				dy = 1
			} else if dy == 0 {
				dx = 1
			}

			key := toKey(dy, dx)
			m[key]++
			if m[key] > maxCnt {
				maxCnt = m[key]
			}
		}

		if maxCnt+same+1 > ans {
			ans = maxCnt + same + 1
		}
	}

	return ans
}

func gcd(a, b int) int {
	// 辗转相除法
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func toKey(dy, dx int) string {
	return fmt.Sprintf("%d/%d", dy, dx)
}

相似题目

题目	难度	考察点
1232. 缀点成线	简单	几何
812. 最大三角形面积	简单	几何
587. 安装栅栏	困难	凸包
447. 回旋镖的数量	中等	哈希表
223. 矩形面积	中等	几何

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/56393194