编程导航会员会员
登录/注册

一文带你学会"最近点对问题"

大家好，我是算法学长，一个热爱分享算法知识的开发者。 算法 0 基础、校招冲刺中大厂，推荐使用算法导航：https://algo.codefather.cn/ 交互式算法学习平台，带大家系统化学习算法。

最近点对问题

介绍

最近点对问题(Closest Pair of Points Problem)是计算几何学中的一个经典问题：给定平面上的n个点，找出其中的一对点，使得它们之间的距离最小。这个问题看似简单，暴力解法可以通过计算所有点对的距离在O(n²)时间内解决，但使用分治策略可以将时间复杂度优化至O(n log n)。该问题在空间索引、聚类分析、碰撞检测等领域有广泛应用。

算法步骤

分治法解决最近点对问题的关键步骤如下：

  1. 分解：
    • 将所有点按照x坐标排序
    • 找到中间点，将点集分为左右两部分
  2. 解决：
    • 递归求解左半部分的最近点对，距离记为δ₁
    • 递归求解右半部分的最近点对，距离记为δ₂
    • 取δ = min(δ₁, δ₂)
  3. 合并：
    • 考虑跨越中线的点对，即一个点在左半部分，一个点在右半部分
    • 只需考虑中线左右各δ距离内的点
    • 对这些点按y坐标排序，对每个点只需与其后最多6个点比较距离
    • 更新最小距离

核心特性

  • 高效性：时间复杂度O(n log n)，优于暴力法的O(n²)
  • 排序预处理：需要按x坐标和y坐标分别排序
  • 空间划分：通过垂直线将平面分为左右两部分
  • 剪枝技术：合并阶段通过几何性质大幅减少比较次数
  • 递归调用：采用递归结构实现分治过程

基础实现

代码实现

Java

▼
java
复制代码
import java.util.*;

class Point {
    double x, y;
    
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
    
    // 计算两点间的欧几里得距离
    public double distance(Point p) {
        return Math.sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
    }
}

public class ClosestPairOfPoints {
    
    // 暴力方法找最近点对
    private static double bruteForce(Point[] points, int start, int end, Point[] closestPair) {
        double minDist = Double.POSITIVE_INFINITY;
        
        for (int i = start; i < end; i++) {
            for (int j = i + 1; j < end; j++) {
                double dist = points[i].distance(points[j]);
                if (dist < minDist) {
                    minDist = dist;
                    if (closestPair != null) {
                        closestPair[0] = points[i];
                        closestPair[1] = points[j];
                    }
                }
            }
        }
        
        return minDist;
    }
    
    // 合并步骤，检查跨越中线的点对
    private static double stripClosest(Point[] strip, int size, double delta, Point[] closestPair) {
        double minDist = delta;
        
        // 按y坐标排序
        Arrays.sort(strip, 0, size, (a, b) -> Double.compare(a.y, b.y));
        
        // 对每个点，只需检查后面y坐标相差小于delta的点
        for (int i = 0; i < size; i++) {
            // 根据几何性质，只需检查最多6个点
            for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < minDist; j++) {
                double dist = strip[i].distance(strip[j]);
                if (dist < minDist) {
                    minDist = dist;
                    if (closestPair != null) {
                        closestPair[0] = strip[i];
                        closestPair[1] = strip[j];
                    }
                }
            }
        }
        
        return minDist;
    }
    
    // 分治法主函数
    private static double closestUtil(Point[] points, int start, int end, Point[] closestPair) {
        int n = end - start;
        
        // 如果点数少于等于3，使用暴力法
        if (n <= 3) {
            return bruteForce(points, start, end, closestPair);
        }
        
        // 找到中间点
        int mid = start + n/2;
        Point midPoint = points[mid];
        
        Point[] leftClosestPair = new Point[2];
        Point[] rightClosestPair = new Point[2];
        
        // 递归解决左右两部分
        double leftDist = closestUtil(points, start, mid, leftClosestPair);
        double rightDist = closestUtil(points, mid, end, rightClosestPair);
        
        // 取左右两部分的最小距离
        double delta = Math.min(leftDist, rightDist);
        Point[] currentClosestPair = (leftDist <= rightDist) ? leftClosestPair : rightClosestPair;
        if (closestPair != null) {
            closestPair[0] = currentClosestPair[0];
            closestPair[1] = currentClosestPair[1];
        }
        
        // 创建strip数组，存储中线附近的点
        Point[] strip = new Point[n];
        int j = 0;
        for (int i = start; i < end; i++) {
            if (Math.abs(points[i].x - midPoint.x) < delta) {
                strip[j++] = points[i];
            }
        }
        
        // 检查strip中是否有更近的点对
        Point[] stripClosestPair = new Point[2];
        double stripDist = stripClosest(strip, j, delta, stripClosestPair);
        
        // 更新最终结果
        if (stripDist < delta) {
            delta = stripDist;
            if (closestPair != null) {
                closestPair[0] = stripClosestPair[0];
                closestPair[1] = stripClosestPair[1];
            }
        }
        
        return delta;
    }
    
    // 查找最近点对的主方法
    public static double closest(Point[] points, Point[] closestPair) {
        int n = points.length;
        
        // 按x坐标排序
        Arrays.sort(points, (a, b) -> Double.compare(a.x, b.x));
        
        // 调用递归函数
        return closestUtil(points, 0, n, closestPair);
    }
}

Python

▼
python
复制代码
import math

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def distance(self, p):
        """计算两点间的欧几里得距离"""
        return math.sqrt((self.x - p.x) ** 2 + (self.y - p.y) ** 2)

def brute_force(points, start, end, closest_pair=None):
    """暴力方法找最近点对"""
    min_dist = float('inf')
    
    for i in range(start, end):
        for j in range(i + 1, end):
            dist = points[i].distance(points[j])
            if dist < min_dist:
                min_dist = dist
                if closest_pair is not None:
                    closest_pair[0] = points[i]
                    closest_pair[1] = points[j]
    
    return min_dist

def strip_closest(strip, size, delta, closest_pair=None):
    """合并步骤，检查跨越中线的点对"""
    min_dist = delta
    
    # 按y坐标排序
    strip.sort(key=lambda p: p.y)
    
    # 对每个点，只需检查后面y坐标相差小于delta的点
    for i in range(size):
        j = i + 1
        while j < size and (strip[j].y - strip[i].y) < min_dist:
            dist = strip[i].distance(strip[j])
            if dist < min_dist:
                min_dist = dist
                if closest_pair is not None:
                    closest_pair[0] = strip[i]
                    closest_pair[1] = strip[j]
            j += 1
    
    return min_dist

def closest_util(points, start, end, closest_pair=None):
    """分治法主函数"""
    n = end - start
    
    # 如果点数少于等于3，使用暴力法
    if n <= 3:
        return brute_force(points, start, end, closest_pair)
    
    # 找到中间点
    mid = start + n // 2
    mid_point = points[mid]
    
    left_closest_pair = [None, None]
    right_closest_pair = [None, None]
    
    # 递归解决左右两部分
    left_dist = closest_util(points, start, mid, left_closest_pair)
    right_dist = closest_util(points, mid, end, right_closest_pair)
    
    # 取左右两部分的最小距离
    delta = min(left_dist, right_dist)
    current_closest_pair = left_closest_pair if left_dist <= right_dist else right_closest_pair
    if closest_pair is not None:
        closest_pair[0] = current_closest_pair[0]
        closest_pair[1] = current_closest_pair[1]
    
    # 创建strip数组，存储中线附近的点
    strip = []
    for i in range(start, end):
        if abs(points[i].x - mid_point.x) < delta:
            strip.append(points[i])
    
    # 检查strip中是否有更近的点对
    strip_closest_pair = [None, None]
    strip_dist = strip_closest(strip, len(strip), delta, strip_closest_pair)
    
    # 更新最终结果
    if strip_dist < delta:
        delta = strip_dist
        if closest_pair is not None:
            closest_pair[0] = strip_closest_pair[0]
            closest_pair[1] = strip_closest_pair[1]
    
    return delta

def closest(points, closest_pair=None):
    """查找最近点对的主方法"""
    n = len(points)
    
    # 按x坐标排序
    points.sort(key=lambda p: p.x)
    
    # 调用递归函数
    return closest_util(points, 0, n, closest_pair)

# 测试用例
if __name__ == "__main__":
    points = [
        Point(2, 3),
        Point(12, 30),
        Point(40, 50),
        Point(5, 1),
        Point(12, 10),
        Point(3, 4)
    ]
    
    closest_pair = [None, None]
    min_dist = closest(points, closest_pair)
    
    print(f"最近点对距离: {min_dist}")
    print(f"最近点对: ({closest_pair[0].x}, {closest_pair[0].y}) 和 ({closest_pair[1].x}, {closest_pair[1].y})")

JavaScript

▼
javascript
复制代码
class Point {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
    
    distance(p) {
        return Math.sqrt((this.x - p.x) ** 2 + (this.y - p.y) ** 2);
    }
}

// 暴力方法找最近点对
function bruteForce(points, start, end, closestPair = null) {
    let minDist = Infinity;
    
    for (let i = start; i < end; i++) {
        for (let j = i + 1; j < end; j++) {
            const dist = points[i].distance(points[j]);
            if (dist < minDist) {
                minDist = dist;
                if (closestPair) {
                    closestPair[0] = points[i];
                    closestPair[1] = points[j];
                }
            }
        }
    }
    
    return minDist;
}

// 合并步骤，检查跨越中线的点对
function stripClosest(strip, size, delta, closestPair = null) {
    let minDist = delta;
    
    // 按y坐标排序
    strip.sort((a, b) => a.y - b.y);
    
    // 对每个点，只需检查后面y坐标相差小于delta的点
    for (let i = 0; i < size; i++) {
        for (let j = i + 1; j < size && (strip[j].y - strip[i].y) < minDist; j++) {
            const dist = strip[i].distance(strip[j]);
            if (dist < minDist) {
                minDist = dist;
                if (closestPair) {
                    closestPair[0] = strip[i];
                    closestPair[1] = strip[j];
                }
            }
        }
    }
    
    return minDist;
}

// 分治法主函数
function closestUtil(points, start, end, closestPair = null) {
    const n = end - start;
    
    // 如果点数少于等于3，使用暴力法
    if (n <= 3) {
        return bruteForce(points, start, end, closestPair);
    }
    
    // 找到中间点
    const mid = start + Math.floor(n / 2);
    const midPoint = points[mid];
    
    const leftClosestPair = [null, null];
    const rightClosestPair = [null, null];
    
    // 递归解决左右两部分
    const leftDist = closestUtil(points, start, mid, leftClosestPair);
    const rightDist = closestUtil(points, mid, end, rightClosestPair);
    
    // 取左右两部分的最小距离
    let delta = Math.min(leftDist, rightDist);
    const currentClosestPair = (leftDist <= rightDist) ? leftClosestPair : rightClosestPair;
    if (closestPair) {
        closestPair[0] = currentClosestPair[0];
        closestPair[1] = currentClosestPair[1];
    }
    
    // 创建strip数组，存储中线附近的点
    const strip = [];
    for (let i = start; i < end; i++) {
        if (Math.abs(points[i].x - midPoint.x) < delta) {
            strip.push(points[i]);
        }
    }
    
    // 检查strip中是否有更近的点对
    const stripClosestPair = [null, null];
    const stripDist = stripClosest(strip, strip.length, delta, stripClosestPair);
    
    // 更新最终结果
    if (stripDist < delta) {
        delta = stripDist;
        if (closestPair) {
            closestPair[0] = stripClosestPair[0];
            closestPair[1] = stripClosestPair[1];
        }
    }
    
    return delta;
}

// 查找最近点对的主方法
function closest(points, closestPair = null) {
    const n = points.length;
    
    // 按x坐标排序
    points.sort((a, b) => a.x - b.x);
    
    // 调用递归函数
    return closestUtil(points, 0, n, closestPair);
}

// 测试用例
const points = [
    new Point(2, 3),
    new Point(12, 30),
    new Point(40, 50),
    new Point(5, 1),
    new Point(12, 10),
    new Point(3, 4)
];

const closestPair = [null, null];
const minDist = closest(points, closestPair);

console.log(`最近点对距离: ${minDist}`);
console.log(`最近点对: (${closestPair[0].x}, ${closestPair[0].y}) 和 (${closestPair[1].x}, ${closestPair[1].y})`);

Go

▼
go
复制代码
package main

import (
    "fmt"
    "math"
    "sort"
)

type Point struct {
    x, y float64
}

// 计算两点间的欧几里得距离
func (p Point) distance(q Point) float64 {
    return math.Sqrt((p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y))
}

// 暴力方法找最近点对
func bruteForce(points []Point, start, end int, closestPair *[2]Point) float64 {
    minDist := math.Inf(1)
    
    for i := start; i < end; i++ {
        for j := i + 1; j < end; j++ {
            dist := points[i].distance(points[j])
            if dist < minDist {
                minDist = dist
                if closestPair != nil {
                    closestPair[0] = points[i]
                    closestPair[1] = points[j]
                }
            }
        }
    }
    
    return minDist
}

// 合并步骤，检查跨越中线的点对
func stripClosest(strip []Point, size int, delta float64, closestPair *[2]Point) float64 {
    minDist := delta
    
    // 按y坐标排序
    sort.Slice(strip[:size], func(i, j int) bool {
        return strip[i].y < strip[j].y
    })
    
    // 对每个点，只需检查后面y坐标相差小于delta的点
    for i := 0; i < size; i++ {
        j := i + 1
        for ; j < size && (strip[j].y-strip[i].y) < minDist; j++ {
            dist := strip[i].distance(strip[j])
            if dist < minDist {
                minDist = dist
                if closestPair != nil {
                    closestPair[0] = strip[i]
                    closestPair[1] = strip[j]
                }
            }
        }
    }
    
    return minDist
}

// 分治法主函数
func closestUtil(points []Point, start, end int, closestPair *[2]Point) float64 {
    n := end - start
    
    // 如果点数少于等于3，使用暴力法
    if n <= 3 {
        return bruteForce(points, start, end, closestPair)
    }
    
    // 找到中间点
    mid := start + n/2
    midPoint := points[mid]
    
    leftClosestPair := [2]Point{}
    rightClosestPair := [2]Point{}
    
    // 递归解决左右两部分
    leftDist := closestUtil(points, start, mid, &leftClosestPair)
    rightDist := closestUtil(points, mid, end, &rightClosestPair)
    
    // 取左右两部分的最小距离
    delta := math.Min(leftDist, rightDist)
    currentClosestPair := &leftClosestPair
    if rightDist < leftDist {
        currentClosestPair = &rightClosestPair
    }
    if closestPair != nil {
        closestPair[0] = currentClosestPair[0]
        closestPair[1] = currentClosestPair[1]
    }
    
    // 创建strip数组，存储中线附近的点
    strip := make([]Point, n)
    j := 0
    for i := start; i < end; i++ {
        if math.Abs(points[i].x-midPoint.x) < delta {
            strip[j] = points[i]
            j++
        }
    }
    
    // 检查strip中是否有更近的点对
    stripClosestPair := [2]Point{}
    stripDist := stripClosest(strip, j, delta, &stripClosestPair)
    
    // 更新最终结果
    if stripDist < delta {
        delta = stripDist
        if closestPair != nil {
            closestPair[0] = stripClosestPair[0]
            closestPair[1] = stripClosestPair[1]
        }
    }
    
    return delta
}

// 查找最近点对的主方法
func closest(points []Point, closestPair *[2]Point) float64 {
    n := len(points)
    
    // 按x坐标排序
    sort.Slice(points, func(i, j int) bool {
        return points[i].x < points[j].x
    })
    
    // 调用递归函数
    return closestUtil(points, 0, n, closestPair)
}

func main() {
    points := []Point{
        {2, 3},
        {12, 30},
        {40, 50},
        {5, 1},
        {12, 10},
        {3, 4},
    }
    
    closestPair := [2]Point{}
    minDist := closest(points, &closestPair)
    
    fmt.Printf("最近点对距离: %f\n", minDist)
    fmt.Printf("最近点对: (%f, %f) 和 (%f, %f)\n", 
        closestPair[0].x, closestPair[0].y, closestPair[1].x, closestPair[1].y)
}

C++

▼
cpp
复制代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

struct Point {
    double x, y;
    
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    
    // 计算两点间的欧几里得距离
    double distance(const Point& p) const {
        return std::sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
    }
};

// 暴力方法找最近点对
double bruteForce(std::vector<Point>& points, int start, int end, std::pair<Point, Point>* closestPair = nullptr) {
    double minDist = std::numeric_limits<double>::infinity();
    
    for (int i = start; i < end; i++) {
        for (int j = i + 1; j < end; j++) {
            double dist = points[i].distance(points[j]);
            if (dist < minDist) {
                minDist = dist;
                if (closestPair != nullptr) {
                    *closestPair = {points[i], points[j]};
                }
            }
        }
    }
    
    return minDist;
}

// 合并步骤，检查跨越中线的点对
double stripClosest(std::vector<Point>& strip, int size, double delta, std::pair<Point, Point>* closestPair = nullptr) {
    double minDist = delta;
    
    // 按y坐标排序
    std::sort(strip.begin(), strip.begin() + size, [](const Point& a, const Point& b) {
        return a.y < b.y;
    });
    
    // 对每个点，只需检查后面y坐标相差小于delta的点
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < minDist; j++) {
            double dist = strip[i].distance(strip[j]);
            if (dist < minDist) {
                minDist = dist;
                if (closestPair != nullptr) {
                    *closestPair = {strip[i], strip[j]};
                }
            }
        }
    }
    
    return minDist;
}

// 分治法主函数
double closestUtil(std::vector<Point>& points, int start, int end, std::pair<Point, Point>* closestPair = nullptr) {
    int n = end - start;
    
    // 如果点数少于等于3，使用暴力法
    if (n <= 3) {
        return bruteForce(points, start, end, closestPair);
    }
    
    // 找到中间点
    int mid = start + n/2;
    Point midPoint = points[mid];
    
    std::pair<Point, Point> leftClosestPair, rightClosestPair;
    
    // 递归解决左右两部分
    double leftDist = closestUtil(points, start, mid, &leftClosestPair);
    double rightDist = closestUtil(points, mid, end, &rightClosestPair);
    
    // 取左右两部分的最小距离
    double delta = std::min(leftDist, rightDist);
    auto& currentClosestPair = (leftDist <= rightDist) ? leftClosestPair : rightClosestPair;
    if (closestPair != nullptr) {
        *closestPair = currentClosestPair;
    }
    
    // 创建strip数组，存储中线附近的点
    std::vector<Point> strip;
    for (int i = start; i < end; i++) {
        if (std::abs(points[i].x - midPoint.x) < delta) {
            strip.push_back(points[i]);
        }
    }
    
    // 检查strip中是否有更近的点对
    std::pair<Point, Point> stripClosestPair;
    double stripDist = stripClosest(strip, strip.size(), delta, &stripClosestPair);
    
    // 更新最终结果
    if (stripDist < delta) {
        delta = stripDist;
        if (closestPair != nullptr) {
            *closestPair = stripClosestPair;
        }
    }
    
    return delta;
}

// 查找最近点对的主方法
double closest(std::vector<Point>& points, std::pair<Point, Point>* closestPair = nullptr) {
    int n = points.size();
    
    // 按x坐标排序
    std::sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
        return a.x < b.x;
    });
    
    // 调用递归函数
    return closestUtil(points, 0, n, closestPair);
}

int main() {
    std::vector<Point> points = {
        {2, 3},
        {12, 30},
        {40, 50},
        {5, 1},
        {12, 10},
        {3, 4}
    };
    
    std::pair<Point, Point> closestPair;
    double minDist = closest(points, &closestPair);
    
    std::cout << "最近点对距离: " << minDist << std::endl;
    std::cout << "最近点对: (" << closestPair.first.x << ", " << closestPair.first.y 
              << ") 和 (" << closestPair.second.x << ", " << closestPair.second.y << ")" << std::endl;
    
    return 0;
}

优缺点

优点

  • 高效性：O(n log n)的时间复杂度，适合处理大规模点集
  • 精确性：能够精确找到最近点对，不是近似算法
  • 可扩展性：可以扩展到三维空间和高维空间
  • 稳定性：算法结果稳定，不依赖于输入点的顺序

缺点

  • 实现复杂：相比暴力法，实现更为复杂
  • 内存消耗：需要额外的空间来存储排序结果和合并阶段的点
  • 递归开销：递归调用带来的额外开销
  • 不易并行化：合并阶段依赖于之前的计算结果，不容易并行处理

应用场景

  • 空间数据库：用于空间索引和最近邻查询
  • 计算几何学：作为基础算法用于解决其他几何问题
  • 聚类分析：用于确定数据点之间的相似性
  • 图像处理：用于特征点匹配和目标识别
  • 碰撞检测：在物理模拟和游戏中检测物体间的碰撞
  • 无线网络：优化节点间的通信距离

扩展

三维空间中的最近点对问题

在三维空间中，最近点对问题的分治算法核心思想与上述相似，但实现更为复杂：

  1. 按x坐标排序并分割点集
  2. 递归计算左右两部分的最近点对
  3. 合并阶段考虑位于中间平面附近的点
  4. 使用三维的剪枝技术减少比较次数

三维空间中，剪枝技术变得更为复杂，需要使用格子或八叉树等空间数据结构来优化。时间复杂度在最坏情况下仍为O(n log n)。

近似算法和概率算法

对于高维空间或对性能要求极高的应用，可以使用近似算法：

  1. 网格方法：将空间划分为网格，只比较同一网格和相邻网格中的点
  2. KD树索引：使用KD树存储点，能在平均O(log n)时间内找到近似最近点
  3. 随机采样：使用随机抽样技术，以牺牲一定精度换取更高效率

流数据处理

在流数据环境中，点是动态添加的，需要维护当前的最近点对：

  1. 使用平衡二叉树维护点的x和y坐标排序
  2. 对新加入的点，只需检查其与附近点的距离
  3. 维护一个候选点集合，保持其大小在O(log n)级别

并行化实现

对于大规模数据，可以采用并行化策略：

  1. 将点集分成多个子集，并行计算每个子集的最近点对
  2. 合并阶段需要考虑跨越不同子集边界的点对
  3. 使用区域重叠技术减少子集边界问题

实际测试表明，在多核环境下，并行实现可以获得接近线性的加速比。

最远点对问题

与最近点对问题相关的是最远点对问题，即找出点集中相距最远的一对点。这个问题可以使用凸包算法解决：

  1. 计算点集的凸包
  2. 在凸包顶点中找出距离最远的点对（可以使用旋转卡尺算法）

最远点对问题的时间复杂度也是O(n log n)，主要受限于凸包计算的复杂度。

测验

  1. 解释为什么在最近点对问题的合并阶段，对于跨越中线的每个点，只需检查y坐标差小于δ的有限个点？
  2. 最近点对算法的合并阶段中，为什么我们可以断言每个点只需与其后最多6个点比较距离？请从几何角度证明。
  3. 如果二维平面上有n个点，其中存在m对相同的点(m < n/2)，最近点对算法的时间复杂度会发生什么变化？如何优化？
  4. 分析最近点对算法在最坏情况下的空间复杂度，并思考如何减少空间消耗。

测验答案

  1. 在合并阶段，我们已经知道左右两部分的最小距离δ，对于跨越中线的点对，如果两点的y坐标差大于δ，那么它们之间的距离一定大于δ（毕竟欧几里得距离公式中，y坐标差的平方是总距离平方的一部分）。因此，我们只需检查y坐标差小于δ的点对，这大大减少了需要比较的点对数量。
  2. 考虑跨越中线的点集，每个点左右δ距离内的区域形成宽度为2δ、高度为2δ的正方形区域。根据鸽巢原理，如果在这个区域中放置超过8个点，必然有两点间距离小于δ（可以将正方形划分为4个边长为δ的小正方形，每个小正方形最多容纳1个点，否则两点距离小于δ）。但这与我们已知的左右两部分最小距离为δ矛盾。更精确的分析表明，每个点实际上最多需要与其后6个点比较距离。
  3. 如果存在相同的点，最小距离为0。算法可以在初始排序后检测相邻点是否重合，如发现重合点立即返回0距离。时间复杂度仍为O(n log n)，主要由排序决定，但实际运行时间会因提前终止而减少。可以使用哈希表预处理，以O(n)时间检测重合点。
  4. 最坏情况下，空间复杂度为O(n)，主要用于递归调用栈(O(log n))和合并阶段的strip数组(O(n))。可以通过迭代实现替代递归，或使用原地排序算法减少辅助数组空间，但这会增加实现复杂度。

相关的 LeetCode 热门题目

学算法就上算法导航：https://algo.codefather.cn/ ，交互式算法学习平台！

算法
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
算法学长
算法学长
等级vip
内容推荐
更多
最近刷算法的一些心得~
6
Claude Code 源码架构深度解析：1884 个文件背后的 AI 编程工具设计哲学
23
深度解析 Claude Code 记忆系统：从源码看 AI 编程助手如何"记住"你的项目
6
LeetCode Hot 100 二分查找篇 - 每次砍一半，六道题从入门到穿透
2
卷AI、卷算法、2026 年的前端工程师到底在卷什么？
7
作者分享
更多
一文带你学会"分治算法"
4
一文带你学会"KMP 算法"
6
一文带你学会"Boyer-Moore算法"
3
一文带你学会"Rabin-Karp算法"
3
一文带你学会"哈希查找"
2
下载 APP