专栏首页Michael阿明学习之路程序员面试金典 - 面试题 16.14. 最佳直线(哈希map+set)

程序员面试金典 - 面试题 16.14. 最佳直线(哈希map+set)

1. 题目

给定一个二维平面及平面上的 N 个点列表Points,其中第i个点的坐标为Points[i]=[Xi,Yi]。 请找出一条直线,其通过的点的数目最多

设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S,你仅需返回[S[0],S[1]]作为答案 若有多条直线穿过了相同数量的点,则选择S[0]值较小的直线返回,S[0]相同则选择S[1]值较小的直线返回。

示例:
输入: [[0,0],[1,1],[1,0],[2,0]]
输出: [0,2]
解释: 所求直线穿过的3个点的编号为[0,2,3]

提示:
2 <= len(Points) <= 300
len(Points[i]) = 2

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/best-line-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 暴力法,固定一个点,遍历所有剩余的
  • 采用嵌套的哈希map,第一层key存储斜率,第二层key存储截距,value为点的set集合(存储下标)
  • 斜率不存在,单独再开一个哈希表,key为与 x 轴的截距,value为点集合
  • 遍历所有集合找最多的
  • 对相等长度的点集合排序,取出题目要求的最小的下标的
  • 时间复杂度 O(n2)O(n^2)O(n2)
class Solution {
public:
    vector<int> bestLine(vector<vector<int>>& points) {
    	int i, j, g, dx, dy, maxCount = 0, n = points.size();
    	double k, b;
    	unordered_map<double,unordered_map<double,set<int>>> m;//k,b,points
    	unordered_map<double,set<int>> v;//x轴截距,斜率不存在时的集合
        vector<set<int>> ans;
    	for(i = 0; i < n-1; ++i)
    	{
    		for(j = i+1; j < n; ++j)
    		{
    			dx = points[j][0]-points[i][0];
    			dy = points[j][1]-points[i][1];
    			if(dx==0)//斜率不存在
    			{
    				if(v[double(points[i][0])].empty())
    					v[double(points[i][0])].insert(i);
    				v[double(points[i][0])].insert(j);
    			}
    			else
    			{
    				k = double(dy)/dx;
    				b = double(points[i][1])-points[i][0]*k;
    				if(m[k][b].empty())
    					m[k][b].insert(i);
    				m[k][b].insert(j);
    			}
    		}
    	}
    	for(auto& mi : m)
    	{
    		for(auto& mii : mi.second)
    		{
                if(mii.second.size() > maxCount)
                {
                    maxCount = mii.second.size();
                    ans.clear();
                    ans.push_back(mii.second);
                }
                else if(mii.second.size() == maxCount)
                    ans.push_back(mii.second);
    		}
    	}
    	for(auto& vi : v)
    	{
    		if(vi.second.size() > maxCount)
			{
				maxCount = vi.second.size();
                ans.clear();
				ans.push_back(vi.second);
			}
            else if(vi.second.size() == maxCount)
                ans.push_back(vi.second);
    	}
        sort(ans.begin(),ans.end(),[&](auto a, auto b){
            auto it1 = a.begin(), it2 = b.begin();
            if(*it1 == *it2)
                return *(++it1) < *(++it2);
            return *it1 < *it2;
        });
        auto it = ans[0].begin();
    	return {*it,*(++it)};
    }
};

660 ms 117.7 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员面试金典 - 面试题 16.22. 兰顿蚂蚁(deque模拟)

    一只蚂蚁坐在由白色和黑色方格构成的无限网格上。 开始时,网格全白,蚂蚁面向右侧。 每行走一步,蚂蚁执行以下操作。

    Michael阿明
  • LeetCode 984. 不含 AAA 或 BBB 的字符串(贪心)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/string-without-aaa-or-bbb ...

    Michael阿明
  • LeetCode 229. 求众数 II(摩尔投票)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/majority-element-ii 著作权归领扣...

    Michael阿明
  • iOS应用程序生命周期(前后台切换,应用的各种状态)详解

    iOS的应用程序的生命周期,还有程序是运行在前台还是后台,应用程序各个状态的变换,这些对于开发者来说都是很重要的。 iOS系统的资源是有限的,应用程序在前台和在...

    猿人谷
  • -Dominant Character

    题目链接 题意:给你一个长度为n字符串,求最小的长度m,使得字符串中所有长度为m的子字符串中均包含某一种字符。 二分模拟计算–

    杨鹏伟
  • 数数字

    把前n(n<=10000)个整数顺次写在一起:123456789101112...数一数0-9各出现多少次(输出10个整数,分别是0,1,...,9出现的次数)...

    Vincent-yuan
  • 爬取美团网站信息(四)

    前几周爬的时候被封过ip,然后就是一直不能获取到详细数据,都是简要的数据,试过好多方法(selenium+PhantomJS、代理ip、ua池),一直没能解决,

    andrew_a
  • Android Studio 3.6 调试 smali的全过程

    Smali是用于Dalvik(Android虚拟机)的反汇编程序实现,汇编工具(将Smali代码汇编为dex文件)为smali.jar,与之对应的baksmal...

    砸漏
  • python中redis查看剩余过期时间以及用正则通配符批量删除key的方法

    用户1214487
  • 接口测试基础——第6篇unittest模块(二)

    用户2149234

扫码关注云+社区

领取腾讯云代金券