题目
给出二维平面上的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 最多有多少个点在一条直线上的更多相关文章
-
149. Max Points on a Line *HARD* 求点集中在一条直线上的最多点数
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. ...
-
[LintCode] 最多有多少个点在一条直线上
/** * Definition for a point. * struct Point { * int x; * int y; * Point() : x(0), y(0) {} * Point(i ...
-
[Swift]LeetCode149. 直线上最多的点数 | 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. ...
-
Max Points on a Line(直线上最多的点数)
给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上. 示例 1: 输入: [[1,1],[2,2],[3,3]] 输出: 3 解释: ^ | | o | o | ...
-
[LintCode] 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. ...
-
[leetcode]Max Points on a Line @ Python
原题地址:https://oj.leetcode.com/problems/max-points-on-a-line/ 题意:Given n points on a 2D plane, find th ...
-
【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 ...
-
[LeetCode OJ] Max Points on a Line
Max Points on a Line Submission Details 27 / 27 test cases passed. Status: Accepted Runtime: 472 ms ...
-
【leetcode】Max Points on a Line(hard)☆
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. ...
随机推荐
-
javascript数组查重方法总结
文章参考地址:http://blog.csdn.net/chengxuyuan20100425/article/details/8497277 题目 对下列数组去重: var arr = ['aa', ...
-
javascript 核心语言笔记 5 - 语句
表达式在 JavaScript 中是短语(phrases),那么语句(statements)就是 JavaScript 整句或命令,语句以分号结束.表达式计算出一个值,语句用来执行以使某件事情发生 表 ...
-
依赖倒置(DIP)与依赖注入(DI)
依赖倒置原则(Dependency Inversion Principle)为我们提供了降低模块间耦合度的一种思路,依赖注入(Dependency Injection)是一种具体的实施方法. 依赖倒置 ...
-
highcharts的简单使用
在使用过的图表js插件中,个人认为还是highcharts最好,无论从兼容性,渲染速度,甚至是文档详细上来说,都一直觉得highcharts更胜一筹.现在花点时间做一下简单的总结,比如从一个矩形图开始 ...
-
Oracle误删除表数据后的恢复具体解释
Oracle误删除表数据后的恢复具体解释 測试环境: SYSTEM:IBM AIX 5L Oracle Version:10gR2 1. undo_re ...
-
css hack 如何区分 ie7 ie8
.style { width:100px; /*火狐以及一般浏览器*/ width:200px\9; /*IE8*/ *width:150px; /*IE7*/ _width:50px; /*IE6* ...
-
mysql进阶(三)游标简易教程
mysql游标简易教程 从mysql V5.5开始,进行了一次大的改变,就是将InnoDB作为默认的存储引擎.InnoDB支持事务,而且拥有相关的RDBMS特性:ACID事务支持,数据完整性(支持外键 ...
-
C++中的虚函数表是什么时期建立的?
虚函数表是在什么时期建立的? 最近参加阿里巴巴公司的内推,面试官问了“虚函数表是在什么时期建立的?”.因为以前对虚函数表的理解不够多,所以就根据程序构建(Build)的四个过程(预编译.编译.汇编和链 ...
-
在 sql server 中,查询 数据库的大小 和 数据库中各表的大小
其实本来只想找一个方法能查询一下 数据库 的大小,没想到这个方法还能查询数据库中 各个数据表 的大小,嗯,挺好玩的,记录一下. MSDN资料:https://msdn.microsoft.com/zh ...
-
习题 6 字符串(string)和文本
虽然你已经在程序中写过字符串了,你还没学过它们的用处.在这章习题中我们将使用复杂的字符串来建立一系列的变量,从中你将学到它们的用途.首先我们解释一下字符串是什么 东西. 字符串通常是指你想要展示给别人 ...