直线上最多的点数

149. 直线上最多的点数

给你一个数组 points ，其中 points[i] = [x_i, y_i] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

提示：

1 <= points.length <= 300
points[i].length == 2
-10⁴ <= x_i, y_i <= 10⁴
points 中的所有点 互不相同

相似题目

直线镜像

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxPoints(vector<vector<int>>& points) { } };

rust 解法, 执行用时: 20 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-22 10:47:27

use std::collections::HashMap;

trait GCD<Rhs = Self> {
    type Output;
    fn gcd(self, num: Rhs) -> Self::Output;
}
impl GCD for i32 {
    type Output = Self;
    fn gcd(self, num: i32) -> i32 {
        let mut p = [self, num];
        while p[1] != 0 {
            p = [p[1], p[0] % p[1]];
        }
        p[0].abs()
    }
}

impl Solution {
    pub fn k(point_i: &[i32], point_j: &[i32]) -> (i32, i32) {
        let mut delta_x = point_i[0] - point_j[0];
        let mut delta_y = point_i[1] - point_j[1];
        if delta_x < 0 {
            delta_x = -delta_x;
            delta_y = -delta_y;
        } else if delta_x == 0 {
            delta_y = delta_y.abs();
        }
        let g = delta_x.gcd(delta_y);
        (delta_x / g, delta_y / g)
    }
    pub fn max_points(points: Vec<Vec<i32>>) -> i32 {
        let mut res = 0;
        for (i, point_i) in points.iter().enumerate() {
            let mut m = HashMap::new();
            let mut cnt = 0;
            for point_j in points.iter().skip(i + 1) {
                let k = Self::k(point_i, point_j);
                m.entry(k).and_modify(|x| *x += 1).or_insert(1);
                cnt = cnt.max(m[&k]);
            }
            res = res.max(cnt + 1);
        }
        res
    }
}

python3 解法, 执行用时: 100 ms, 内存消耗: 16 MB, 提交时间: 2023-09-22 10:47:09

class Solution:
    @staticmethod
    def k(point_i: List[int], point_j: List[int]) -> (int, int):
        delta_x = point_i[0] - point_j[0]
        delta_y = point_i[1] - point_j[1]
        if delta_x < 0:
            delta_x = -delta_x
            delta_y = -delta_y
        elif delta_x == 0:
            delta_y = abs(delta_y)
        g = math.gcd(delta_x, delta_y)
        return delta_x // g, delta_y // g

    def maxPoints(self, points: List[List[int]]) -> int:
        res = 0
        for i, point_i in enumerate(points):
            m = {}
            cnt = 0
            for point_j in points[i + 1:]:
                k = self.k(point_i, point_j)
                if k in m:
                    m[k] += 1
                else:
                    m[k] = 1
                cnt = max(cnt, m[k])
            res = max(res, cnt + 1)
        return res

golang 解法, 执行用时: 8 ms, 内存消耗: 6.1 MB, 提交时间: 2023-09-22 10:46:42

func maxPoints(points [][]int) (ans int) {
    n := len(points)
    if n <= 2 {
        return n
    }
    for i, p := range points {
        if ans >= n-i || ans > n/2 {
            break
        }
        cnt := map[int]int{}
        for _, q := range points[i+1:] {
            x, y := p[0]-q[0], p[1]-q[1]
            if x == 0 {
                y = 1
            } else if y == 0 {
                x = 1
            } else {
                if y < 0 {
                    x, y = -x, -y
                }
                g := gcd(abs(x), abs(y))
                x /= g
                y /= g
            }
            cnt[y+x*20001]++
        }
        for _, c := range cnt {
            ans = max(ans, c+1)
        }
    }
    return
}

func gcd(a, b int) int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

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

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

javascript 解法, 执行用时: 68 ms, 内存消耗: 43.8 MB, 提交时间: 2023-09-22 10:46:05

/**
 * @param {number[][]} points
 * @return {number}
 */
var maxPoints = function(points) {
    const n = points.length;
    if (n <= 2) {
        return n;
    }
    let ret = 0;
    for (let i = 0; i < n; i++) {
        if (ret >= n - i || ret > n / 2) {
            break;
        }
        const map = new Map();
        for (let j = i + 1; j < n; j++) {
            let x = points[i][0] - points[j][0];
            let y = points[i][1] - points[j][1];
            if (x === 0) {
                y = 1;
            } else if (y === 0) {
                x = 1;
            } else {
                if (y < 0) {
                    x = -x;
                    y = -y;
                }
                const gcdXY = gcd(Math.abs(x), Math.abs(y));
                x /= gcdXY;
                y /= gcdXY;
            }
            const key = y + x * 20001;
            map.set(key, (map.get(key) || 0)+ 1);
        }
        let maxn = 0;
        for (const num of map.values()) {
            maxn = Math.max(maxn, num + 1);
        }
        ret = Math.max(ret, maxn);
    }
    return ret;
};

const gcd = (a, b) => {
    return b != 0 ? gcd(b, a % b) : a;
}

java 解法, 执行用时: 23 ms, 内存消耗: 41.9 MB, 提交时间: 2023-09-22 10:45:42

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) {
            return n;
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (ret >= n - i || ret > n / 2) {
                break;
            }
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for (int j = i + 1; j < n; j++) {
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                if (x == 0) {
                    y = 1;
                } else if (y == 0) {
                    x = 1;
                } else {
                    if (y < 0) {
                        x = -x;
                        y = -y;
                    }
                    int gcdXY = gcd(Math.abs(x), Math.abs(y));
                    x /= gcdXY;
                    y /= gcdXY;
                }
                int key = y + x * 20001;
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
            int maxn = 0;
            for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
                int num = entry.getValue();
                maxn = Math.max(maxn, num + 1);
            }
            ret = Math.max(ret, maxn);
        }
        return ret;
    }

    public int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}

cpp 解法, 执行用时: 28 ms, 内存消耗: 12.3 MB, 提交时间: 2023-09-22 10:45:20

class Solution {
public:
    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    }

    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 2) {
            return n;
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (ret >= n - i || ret > n / 2) {
                break;
            }
            unordered_map<int, int> mp;
            for (int j = i + 1; j < n; j++) {
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                if (x == 0) {
                    y = 1;
                } else if (y == 0) {
                    x = 1;
                } else {
                    if (y < 0) {
                        x = -x;
                        y = -y;
                    }
                    int gcdXY = gcd(abs(x), abs(y));
                    x /= gcdXY, y /= gcdXY;
                }
                mp[y + x * 20001]++;
            }
            int maxn = 0;
            for (auto& [_, num] : mp) {
                maxn = max(maxn, num + 1);
            }
            ret = max(ret, maxn);
        }
        return ret;
    }
};

上一题

下一题

详情