lintcode 中等题:Max Points on a Line 最多有多少个点在一条直线上

时间:2022-03-20 22:42:53

题目

给出二维平面上的n个点,求最多有多少点在同一条直线上。

样例

给出4个点:(1, 2)(3, 6)(0, 0)(1, 3)

一条直线上的点最多有3个。

解题

直接暴力求解有问题,时间复杂度O(N3),对其中的相同点没有处理,斜率为0,不存在也没有处理,找出运行不对

看到通过定义一个HashMap存储直线的斜率,存在相同的情况就+ 1 ,最后找到斜率个数最长的那个。

下面程序中已经有很多注释了。

 /**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
/**
* @param points an array of point
* @return an integer
*/
public int maxPoints(Point[] points) {
// Write your code here
if(points == null)
return 0;
int m = points.length;
if(m == 0)
return 0;
if( m <= 2)
return m;
int maxline = 0;
HashMap<Double,Integer> map = new HashMap<Double,Integer>();
for(int i = 0 ;i < m ; i ++){
map.clear();
// dup 是记录和当前点i相同的点的个数,注意这里不包括当前点 i
int dup = 0;
for(int j = i + 1; j < m ;j++){
// 出来相同的点
if(points[i].x == points[j].x && points[i].y == points[j].y){
dup ++;
continue;
}
// 处理斜率不存在的情况
double k = points[i].x==points[j].x ?Integer.MAX_VALUE:
(0.0+ points[i].y-points[j].y)/(points[i].x-points[j].x)*1.0; if(map.containsKey(k)){
map.put(k,map.get(k)+1); // 这里是新的j点,只需 + 1
}else{
map.put(k,2); // i j 两个点所在的直线,有两个点
}
}
// 全部相同的情况
if(map.size()==0){
// 需要加上当前点
maxline = Math.max(maxline,dup + 1 );
}else{
for(int tmp:map.values()){
if(tmp+dup>maxline)
maxline = tmp+dup; }
} }
return maxline;
}
}

Java Code

# Definition for a point.
# class Point:
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b class Solution:
# @param {int[]} points an array of point
# @return {int} an integer
def maxPoints(self, points):
# Write your code here
if points == None :
return 0
m = len(points)
if m <= 2:
return m
maxline = 0
for i in range(m):
dup = 1
d = {}
d['inf'] = 0
for j in range((i+1),m):
if points[i].x == points[j].x and points[j].y == points[i].y:
dup +=1
elif points[j].x == points[i].x:
d['inf'] += 1
else:
k = 1.0*(points[j].y - points[i].y)/(points[j].x - points[i].x)
if k in d:
d[k] += 1
else:
d[k] = 1
maxline = max( max(d.values()) + dup,maxline) return maxline

Python Code

lintcode 中等题:Max Points on a Line 最多有多少个点在一条直线上的更多相关文章

  1. 149&period; Max Points on a Line &ast;HARD&ast; 求点集中在一条直线上的最多点数

    Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. ...

  2. &lbrack;LintCode&rsqb; 最多有多少个点在一条直线上

    /** * Definition for a point. * struct Point { * int x; * int y; * Point() : x(0), y(0) {} * Point(i ...

  3. &lbrack;Swift&rsqb;LeetCode149&period; 直线上最多的点数 &vert; Max Points on a Line

    Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. ...

  4. Max Points on a Line(直线上最多的点数)

    给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上. 示例 1: 输入: [[1,1],[2,2],[3,3]] 输出: 3 解释: ^ | |        o |     o | ...

  5. &lbrack;LintCode&rsqb; Max Points on a Line 共线点个数

    Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. ...

  6. &lbrack;leetcode&rsqb;Max Points on a Line &commat; Python

    原题地址:https://oj.leetcode.com/problems/max-points-on-a-line/ 题意:Given n points on a 2D plane, find th ...

  7. 【leetcode】Max Points on a Line

    Max Points on a Line 题目描述: Given n points on a 2D plane, find the maximum number of points that lie ...

  8. &lbrack;LeetCode OJ&rsqb; Max Points on a Line

    Max Points on a Line Submission Details 27 / 27 test cases passed. Status: Accepted Runtime: 472 ms ...

  9. 【leetcode】Max Points on a Line(hard)&star;

    Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. ...

随机推荐

  1. javascript数组查重方法总结

    文章参考地址:http://blog.csdn.net/chengxuyuan20100425/article/details/8497277 题目 对下列数组去重: var arr = ['aa', ...

  2. javascript 核心语言笔记 5 - 语句

    表达式在 JavaScript 中是短语(phrases),那么语句(statements)就是 JavaScript 整句或命令,语句以分号结束.表达式计算出一个值,语句用来执行以使某件事情发生 表 ...

  3. 依赖倒置(DIP)与依赖注入(DI)

    依赖倒置原则(Dependency Inversion Principle)为我们提供了降低模块间耦合度的一种思路,依赖注入(Dependency Injection)是一种具体的实施方法. 依赖倒置 ...

  4. highcharts的简单使用

    在使用过的图表js插件中,个人认为还是highcharts最好,无论从兼容性,渲染速度,甚至是文档详细上来说,都一直觉得highcharts更胜一筹.现在花点时间做一下简单的总结,比如从一个矩形图开始 ...

  5. Oracle误删除表数据后的恢复具体解释

    Oracle误删除表数据后的恢复具体解释 測试环境: SYSTEM:IBM AIX 5L                         Oracle Version:10gR2 1. undo_re ...

  6. css hack 如何区分 ie7 ie8

    .style { width:100px; /*火狐以及一般浏览器*/ width:200px\9; /*IE8*/ *width:150px; /*IE7*/ _width:50px; /*IE6* ...

  7. mysql进阶&lpar;三&rpar;游标简易教程

    mysql游标简易教程 从mysql V5.5开始,进行了一次大的改变,就是将InnoDB作为默认的存储引擎.InnoDB支持事务,而且拥有相关的RDBMS特性:ACID事务支持,数据完整性(支持外键 ...

  8. C&plus;&plus;中的虚函数表是什么时期建立的?

    虚函数表是在什么时期建立的? 最近参加阿里巴巴公司的内推,面试官问了“虚函数表是在什么时期建立的?”.因为以前对虚函数表的理解不够多,所以就根据程序构建(Build)的四个过程(预编译.编译.汇编和链 ...

  9. 在 sql server 中,查询 数据库的大小 和 数据库中各表的大小

    其实本来只想找一个方法能查询一下 数据库 的大小,没想到这个方法还能查询数据库中 各个数据表 的大小,嗯,挺好玩的,记录一下. MSDN资料:https://msdn.microsoft.com/zh ...

  10. 习题 6 字符串&lpar;string&rpar;和文本

    虽然你已经在程序中写过字符串了,你还没学过它们的用处.在这章习题中我们将使用复杂的字符串来建立一系列的变量,从中你将学到它们的用途.首先我们解释一下字符串是什么 东西. 字符串通常是指你想要展示给别人 ...