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

题目是这样的，given a list of points in 2D space （可能有重复点）, 所有的点的坐标都是integer。given an integer k。找到最小的square正方形，使得
1. 正方形的四个顶点的x坐标和y坐标也都是Integer
2. 正方形的内部（不包括边上）有至少k个点。

比如list是 [[1,1],[2,2]], k=2, 就需要一个左下角在[0,0] 右上角在[3,3]的正方形来包括这两个点。

除了brute force完全没想法，求大神给思路。

二维前缀和维护正方形中点的个数，对正方形边长进行二分答案。

老哥你得给下数据范围啊?不给怎么估计时间复杂度啊?第一反应是枚举起点point,然后二分答案length.显然有一个length满足以这个起点,长为length的正方形中有k个点时,大于length的正方形也满足要求,具有单调性满足二分条件.问题就转变为如何快速求以point为端点,length为边长的正方形内点的个数.考虑对区域这样划分:
  a  |  b
----|----  末端
  c  |  d
   末端
使用前缀和维护x轴,y轴点的个数.显然有a区域点的个数=a到x轴末端前缀和-b到x轴末端前缀和-c到y轴末端前缀和+d区域点的个数
时间复杂度O(nlogk)n为点的个数,k为坐标上下限差的绝对值

补充内容 (2021-06-27 09:20 +8:00):
P.S. 更正一下,之前一维前缀和的思路是错的,还是需要使用二维前缀和,时间复杂度也应该是O(n^2logk)

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

时间复杂度N^2logC

我觉得首先要找到 list里面所有的二维点的 最大和最小 的x和y——> 确定范围

补充内容 (2021-06-25 11:10 +08:00):
然后max + 1 不就行了？

天连夜月 发表于 2021-06-24 20:10:38
我觉得首先要找到 list里面所有的二维点的 最大和最小 的x和y——> 确定范围

补充内容 (2021-06-25 11:10 +08:00):

我例子举的不好。不是覆盖所有点，是至少覆盖k个点，k可能比list长度要小。

一维的很简单，就是如果小于k就挪r，大于k就挪l。
对于二维可以简化为1维，对于每条对角线都做一次，如果里面大于k个点，把左上角网右下移一个。如果小于k个，把右下往右下自动一个。
只是个思路，系列没想，求轻喷，求加米

如果要包含 [[1,1],[2,2]]，最小的正方形是 [[0,1], [2,3], [4,1], [2,-1]]

dongyao 发表于 2021-06-24 21:03:43
如果要包含 ,]，最小的正方形是 , , , ]

还有个条件是正方形的边必须都是和x轴y轴平行的，忘记说了抱歉

应该是做一个 kdtree，每个点找 k-1 nearest neighbor，每个点加 neighbor 的 max(x-span, y-span)是至少需要包含的（正方形）面积的边长。之后就是给一个这样的正方形，寻找一个最小的可以包含它的正方形（可以是斜的）

用DP?从包含一个点开始，包含两个点的由两个包含一个点的生成，依次递推