Leetcode: 【每日一题】- 2019-09-26 - 寻找最近的点
给定二维平面上N个点的坐标(x, y) ， 找出距离最近的两个点。
如图：
azl397985856
👍2
All 4 comments
用45分钟 没想出来
看别人答案 第三点合并部分没看懂.依然没看懂
思路：把点集分为两半，最近点对可能全部属于左半点集，或者右半点集，或者一个属于左半点集，一个属于右半点集。所以最终结果为这三种情况的最小值。
分治法一般分为三个步骤：
1 分解：将 n 个点按照横坐标排序，并按照 1~n编号， 分成两部分：1~⌊n2⌋、⌈n2⌉~n。
2 解决：分别求出左右两部分中的最近点对距离，记为 d1 和 d2d，取 d=min(d1,d2))。
时间复杂度为 2T(n2) （这里通常采用递归的办法）
3 合并：这一步考虑的问题是，最近点对可能分别来自左半部分点集和右半部分点集，
所以如果存在这样一个最近点对距离比 d 还小，
那么返回该值，否则返回 d。
————————————————
watchpoints
on 27 Sep 2019
👍2
This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.
![stale[bot] picture](https://avatars.githubusercontent.com/in/1724?v=4&s=40)
stale[bot]
on 26 Nov 2019
How can I need added to it
sirvick-tech
on 14 Apr 2020
How can I need added to it
You mean "making a pull request" ? If so, please visite Daily Problem Contribution
azl397985856
on 15 Apr 2020
Was this page helpful?
0 / 5 - 0 ratings
Related issues
azl397985856
·
3Comments
azl397985856
·
3Comments
azl397985856
·
4Comments
azl397985856
·
3Comments
azl397985856
·
3Comments
Most helpful comment
用45分钟 没想出来
思路：把点集分为两半，最近点对可能全部属于左半点集，或者右半点集，或者一个属于左半点集，一个属于右半点集。所以最终结果为这三种情况的最小值。
分治法一般分为三个步骤：
1 分解：将 n 个点按照横坐标排序，并按照
1~n编号， 分成两部分：1~⌊n2⌋、⌈n2⌉~n。2 解决：分别求出左右两部分中的最近点对距离，记为 d1 和 d2d，取 d=min(d1,d2))。
时间复杂度为 2T(n2) （这里通常采用递归的办法）
3 合并：这一步考虑的问题是，最近点对可能分别来自左半部分点集和右半部分点集，
所以如果存在这样一个最近点对距离比 d 还小，
那么返回该值，否则返回 d。
————————————————