算法笔试模拟题精解之“平行线”-阿里云开发者社区

 知识中心     |      2020-04-02 00:00:00

在线编程介绍

阿里云开发者社区在线编程产品,针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等,界面整洁明了,操作简单,为用户营造专心答题的学习环境。点击链接开始体验:https://developer.aliyun.com/coding

本文为大家介绍其中的第72题:平行线 的题目解析,具体如下:

题目描述

查看题目:平行线 为了管理动物园不听话的大猩猩们,动物管理员决定去远方的动物之城找一些平行线。
当他逛到一个神奇的店铺时,他发现了一副黑色的图,上面依稀可见一些白色的点。
动物管理员询问店铺老板这幅画是什么,老板说:“天机不可泄露”。动物管理员仔细端详了一会这幅画后,他发现其中的一些白点可以连成两条平行线。
动物管理员问这幅画多少钱,老板说:“原价¥99999999999,但现在你只要计算出来这里面有几对平行线,就可以打折,有几对平行线就价值多少钱”。请你计算出动物管理员最少需要支付多少钱?

输入一个整数n,表示总共有n个点(1 <= n <= 1000);和一个含有n组数据(xi, yi)的数组,(xi, yi)表示二维平面上一个点(1 <= xi,yi <= 1000),且每个点均不重复。

输出n个点能够找出几对平行线。(答案不超过int)
示例1
输入:
6
[[0,0],[1,0],[1,1],[3,1],[3,3],[5,4]]
输出:
10

解题思路:排序问题

任意两点确定一条直线。判断两条直线是否平行就是比较两条直线的斜率。这道题对于由不同的点确定的但是重合在一起的直线应该也判断为一组平行线。
一共有n个点,就有n*(n-1)/2条直线。对于点i和j确定的直线斜率为(yi-yj)/(xi-xj).
使用一个数组保存斜率,然后排序。
排序过后相同斜率的直线就在连续的位置了。
假设斜率为k的直线有a条,对应着有a*(a-1)/2组平行线(任意两条相互平行)。
遍历一次排序后的数组就可以得到结果。
使用简单的冒泡排序可能会超时,考虑更快的快速排序,归并排序或者直接使用java的排序函数。
时间空间复杂度与排序算法有关。

看完之后是不是有了想法了呢,快来练练手吧>>查看题目
image.png