【算法进阶】从一维到二维：分治算法彻底搞定「最接近点对问题」（C++ 完整实现 + 超详细讲解）

前言在算法设计中分治算法是解决复杂问题的核心思想之一分解 - 解决 - 合并把大问题拆成同类小问题递归求解后汇总结果。最接近点对问题是分治的经典面试 / 作业题很多同学一上来就看二维代码会非常懵。本文采用循序渐进的方式先讲一维数组最简单入门- 提炼分治思想 - 升级到二维平面结合你完整的 C 代码逐行讲解关键逻辑、设计原因、实现原理让你彻底吃透这个算法一、先看最简单一维数组中的最接近点对1. 问题描述给定一个一维数组找出数组中差值最小的两个数。暴力解法遍历所有数对O(n2)分治解法O(nlogn)2. 一维分治核心思路最关键划分把数组按中位数分成左、右两部分求解递归求左边最小差值、右边最小差值合并最关键—— 检查「左边最大值」和「右边最小值」的差值最终得到全局最小值二、一维最接近点对完整代码#includestdio.h #includeiostream #includeassert.h #includestdlib.h #includestring.h #includelimits.h #includestack #includequeue using namespace std; // 一维最接近点对问题 const int ArSize 15; // 生成随机数组 void RandAr(int* ar, int n) { assert(ar ! nullptr); for (int i 0; i n; i) { ar[i] rand() % 100 1; } } // 打印数组 void PrintAr(const int* ar, int n) { assert(ar ! nullptr); for (int i 0; i n; i) { printf(%5d, i); } printf(\n); for (int i 0; i n; i) { printf(%5d, ar[i]); } printf(\n--------------------------\n); } // 快速选择找第k小分治划分的核心 int Partition(int* ar, int left, int right) { assert(ar ! nullptr); int i left, j right; int tmp ar[i]; while (i j) { while (i j ar[j] tmp) --j; ar[i] ar[j]; while (i j ar[i] tmp) i; ar[j] ar[i]; } ar[i] tmp; return i; } // 递归找第k小元素 int SelectKM(int* ar, int left, int right, int k) { if (left right k 1)return ar[left]; int pos Partition(ar, left, right); int j pos - left 1; if (k j)return SelectKM(ar, left, pos, k); else return SelectKM(ar, pos 1, right, k - j); } // 对外接口找第k小 int SelectKMin(int* ar, int n, int k) { assert(ar ! nullptr); if (n 1 || k1 || kn)return -1; return SelectKM(ar, 0, n - 1, k); } // 工具函数 int MinInt(int a, int b) { return a b ? a : b; } int Min3Int(int a, int b, int c) { return MinInt(a, MinInt(b, c)); } // 找S1区间最大值 int MaxS1(const int* ar, int left, int pos) { return ar[pos]; } // 找S2区间最小值 int MinS2(const int* ar, int pos1, int right) { int minv ar[pos1]; for (int i pos 2; i right; i) { if (ar[i] minv) minv ar[i]; } return minv; } // 一维分治主函数 int CpairMin(int* ar, int left, int right) { // 递归终止只有1个点无距离 if (right - left 0) return INT_MAX; // 找中位数位置划分左右 int mid (right - left 1) / 2; int pos left mid - 1; SelectKM(ar, left, right, mid); // 把第mid小放到中间完成划分 // 1. 递归求解左右 int d1 CpairMin(ar, left, pos); // 左区间最小差 int d2 CpairMin(ar, pos 1, right); // 右区间最小差 // 2. 合并检查跨中点的点对左最大 右最小 int p MaxS1(ar, left, pos); int q MinS2(ar, pos 1, right); // 3. 三者取最小左、右、跨区间 return Min3Int(d1, d2, q - p); } // 对外调用接口 int Cpair1(int* ar, int n) { assert(ar ! nullptr); return CpairMin(ar, 0, n - 1); } // 一维测试 int main() { int ar[] { 100,12,45,90,56,67,23,34,13,78,92 }; int n sizeof(ar) / sizeof(ar[0]); int minval Cpair1(ar, n); cout 一维数组最小差值 minval endl; return 0; }三、一维代码关键讲解为什么这么写1. 为什么要用「快速选择找第 k 小」分治需要把数组按中位数分成两部分快速选择可以在 O(n) 时间内把第 k 小放到正确位置保证左区间 ≤ 中位数 ≤ 右区间完美满足分治划分要求2. 递归终止条件if (right - left 0) return INT_MAX;区间内只有 1 个数无法构成点对返回无穷大3. 合并步骤最核心int p 左区间最大值 int q 右区间最小值 int cross q - p一维最接近点对只可能出现在三个地方左边内部右边内部左最大 和 右最小 之间所以三者取最小就是答案四、进阶升级从一维 → 二维平面最接近点对1. 一维 vs 二维 思想完全一致维度划分依据递归求解合并关键一维按中位数划分左右最小差左最大 右最小二维按 x 坐标中值划分左右最小距离跨中线带状区域内点对2. 二维升级难点一维合并只需要检查 1 个点对二维合并需要检查中线附近带状区域但最多只检查 6 个点依旧是常数时间五、二维最接近点对完整代码含一维 二维全套下面把一维基础版 二维进阶版完整整合结构清晰、循序渐进。#includestdio.h #includeiostream #includeassert.h #includestdlib.h #includestring.h #includelimits.h #includefloat.h #includecmath #includestack #includequeue using namespace std; // // 第一部分一维最接近点对 // const int ArSize 15; void RandAr(int* ar, int n) { assert(ar ! nullptr); for (int i 0; i n; i) ar[i] rand() % 100 1; } void PrintAr(const int* ar, int n) { assert(ar ! nullptr); for (int i 0; i n; i) printf(%5d, i); printf(\n); for (int i 0; i n; i) printf(%5d, ar[i]); printf(\n--------------------------\n); } int Partition(int* ar, int left, int right) { assert(ar ! nullptr); int i left, j right; int tmp ar[i]; while (i j) { while (i j ar[j] tmp) --j; ar[i] ar[j]; while (i j ar[i] tmp) i; ar[j] ar[i]; } ar[i] tmp; return i; } int SelectKM(int* ar, int left, int right, int k) { if (left right k 1)return ar[left]; int pos Partition(ar, left, right); int j pos - left 1; if (k j)return SelectKM(ar, left, pos, k); else return SelectKM(ar, pos 1, right, k - j); } int SelectKMin(int* ar, int n, int k) { assert(ar ! nullptr); if (n 1 || k1 || kn)return -1; return SelectKM(ar, 0, n - 1, k); } int MinInt(int a, int b) { return a b ? a : b; } int Min3Int(int a, int b, int c) { return MinInt(a, MinInt(b, c)); } int MaxS1(const int* ar, int left, int pos) { return ar[pos]; } int MinS2(const int* ar, int l, int r) { int m ar[l]; for (int i l 1; i r; i) if (ar[i] m) m ar[i]; return m; } int CpairMin(int* ar, int left, int right) { if (right - left 0) return INT_MAX; int mid (right - left 1) / 2; int pos left mid - 1; SelectKM(ar, left, right, mid); int d1 CpairMin(ar, left, pos); int d2 CpairMin(ar, pos 1, right); int p MaxS1(ar, left, pos); int q MinS2(ar, pos 1, right); return Min3Int(d1, d2, q - p); } int Cpair1(int* ar, int n) { assert(ar ! nullptr); return CpairMin(ar, 0, n - 1); } // // 第二部分二维最接近点对 // struct PointX { int id, x, y; operator int()const { return x; } }; struct PointY { int sid, x, y; operator int()const { return y; } }; templateclass T double Distance(const T a, const T b) { double dx a.x - b.x, dy a.y - b.y; return sqrt(dx * dx dy * dy); } templateclass T void Merge(T* src, T* dest, int L, int M, int R) { int i L, j M 1, k L; while (i M j R) dest[k] src[i] src[j] ? src[i] : src[j]; while (i M) dest[k] src[i]; while (j R) dest[k] src[j]; } templateclass T void MergePass(T* src, T* dest, int s, int n) { int i 0; while (i 2 * s - 1 n - 1) { Merge(src, dest, i, i s - 1, i 2 * s - 1); i 2 * s; } if (i s n - 1) Merge(src, dest, i, i s - 1, n - 1); else for (int j i; j n; j) dest[j] src[j]; } templateclass T void MergeSort(T* ar, int n) { if (!ar || n 1) return; T* br new T[n]; int s 1; while (s n) { MergePass(ar, br, s, n); s * 2; MergePass(br, ar, s, n); s * 2; } delete[] br; } void PrintX(const PointX* X, int n) { for (int i 0; i n; i) printf(%2d - (%2d, %2d)\n, X[i].id, X[i].x, X[i].y); } void closest(PointX X[], PointY Y[], PointY Z[], int L, int R, PointX a, PointX b, double dist) { if (R - L 0) { a.id b.id -1; dist DBL_MAX; return; } if (R - L 1) { a X[L]; b X[R]; dist Distance(a, b); return; } if (R - L 2) { double d1 Distance(X[L], X[L 1]); double d2 Distance(X[L 1], X[R]); double d3 Distance(X[L], X[R]); if (d1 d2 d1 d3) a X[L], b X[L 1], dist d1; else if (d2 d1 d2 d3) a X[L 1], b X[R], dist d2; else a X[L], b X[R], dist d3; return; } int mid (L R) / 2; int f L, g mid 1; for (int i L; i R; i) { if (Y[i].sid mid) Z[g] Y[i]; else Z[f] Y[i]; } closest(X, Z, Y, L, mid, a, b, dist); PointX ar, br; double dr 0; closest(X, Z, Y, mid 1, R, ar, br, dr); if (dr dist) a ar, b br, dist dr; Merge(Z, Y, L, mid, R); int k L; for (int i L; i R; i) if (fabs(Y[mid].x - Y[i].x) dist) Z[k] Y[i]; for (int i L; i k; i) { for (int j i 1; j k Z[j].y - Z[i].y dist; j) { double dp Distance(Z[i], Z[j]); if (dp dist) { a X[Z[i].sid]; b X[Z[j].sid]; dist dp; } } } } bool Cpair2(PointX X[], int n, PointX a, PointX b, double dist) { if (n 2) return false; MergeSort(X, n); PointY* Y new PointY[n]; for (int i 0; i n; i) { Y[i].sid i; Y[i].x X[i].x; Y[i].y X[i].y; } MergeSort(Y, n); PointY* Z new PointY[n]; closest(X, Y, Z, 0, n - 1, a, b, dist); delete[] Y; delete[] Z; return true; } // // 主函数测试 // int main() { cout 测试一维最接近点对 endl; int ar[] { 100,12,45,90,56,67,23,34,13,78,92 }; int n sizeof(ar) / sizeof(ar[0]); cout 一维最小差值 Cpair1(ar, n) endl endl; cout 测试二维最接近点对 endl; const int m 20; PointX X[m]; for (int i 0; i m; i) { X[i].id i; X[i].x rand() % 30; X[i].y rand() % 30; } // 手动设置两个极近点用于测试 X[1].x 5; X[1].y 6; X[15].x 6; X[15].y 6; PrintX(X, m); PointX a { -1,-1,-1 }, b { -1,-1,-1 }; double d 0; bool ok Cpair2(X, m, a, b, d); if (ok) { printf(\n最近点对\n); printf(点aid%d - (%d, %d)\n, a.id, a.x, a.y); printf(点bid%d - (%d, %d)\n, b.id, b.x, b.y); printf(最小距离%.6lf\n, d); } else printf(点数量不足\n); return 0; }六、二维关键代码深度解析1. PointX / PointY 为什么要分开PointX按 x 排序 → 用于划分左右区间PointY按 y 排序 → 用于合并时快速筛选sid建立映射关系保证两个结构体指向同一个点2. 为什么用归并排序稳定排序保证顺序不变时间复杂度 O(nlogn)和分治完美匹配让区间内点始终按 y 有序合并时只检查 O (1) 个点3. 合并时为什么只检查带状区域fabs(Y[mid].x - Y[i].x) dist只有 x 距离中线 当前最小距离的点才可能更近再按 y 排序最多只检查 6 个点合并时间从 O(n2) 直接降到 O(1)七、整体总结最精华一维是基础划分 → 递归 → 检查左最大 右最小二维是升级按 x 划分 → 递归求左右 → 检查带状区域分治思想统一大问题拆小递归求解高效合并复杂度O(nlogn)远优于暴力 O(n2)