某国人无人车公司OA遇到的题没有思路

将所有的点按照y的位置排序。首先二分搜索边长L，再遍历每个点(x0,y0) 当做这个边长为L的正方形的左边界，那么正方形右边界就是x0+L。我们再竖着遍历所有的点，维护一个滑动窗口：窗口里面有效点的数目始终为k（有效的意思是x坐标在[x0,x0+L]范围内），查看这个滑动窗口的y值范围是否小于等于L。如果成立，那么说明边长为L的正方形一定能至少覆盖k个点。

时间复杂度N^2logC

pc1001 发表于 2021-6-25 12:33
还有个条件是正方形的边必须都是和x轴y轴平行的，忘记说了抱歉

没有这个条件的话，乍一看还以为是凸包，但是又要求整数坐标就还挺奇怪的。有这个条件就合理多了。

边和坐标轴平行,正方形边长为 max(DXi, DYi) +2;i=0,1,2...k
先y方向排序，一个方向k个为一组差分(求边长)，然后边长排序。从小到大(必须>=k)，直到找到这一组的x方向的长度小于等于y长度，这一组就是答案？

感觉很像lidar来了一堆点云，然后需要k个点去创建单元，怎么感觉是在套solution。奇奇怪怪的题目。