方法1：兩兩點比較，尋找最近的兩個點對，復(fù)雜度O(N^2)，優(yōu)點代碼簡單不容易出錯

double mindifference(double arr[], int n) {if (n < 2){return 0;}double fmin = fabs(arr[0] - arr[1]);for (int i = 0; i < n; i++){for (int j = i + 1; j < n; j++){double temp = fabs(arr[i] - arr[j]);if (fmin>temp){fmin = temp;}}}return fmin; }
解法2‘、

如果數(shù)組是有序的，找出最小的差值容易了。

double mindifference(double arr[], int n) {if (n < 2){return 0;}sort(arr, arr + n);double fmin = arr[1] - arr[0];for (int i = 2; i < n; i++){double temp = arr[i] - arr[i - 1];if (fmin>temp){fmin = temp;}}return fmin; } 方法3：采用分治法，即從x軸將數(shù)據(jù)不斷分成兩部分，兩部分最近的兩點取其小，在進行兩部分中間比較，通過兩部分的最小距離，縮小了中間帶狀的點數(shù)量，詳見編程之美的分析。

#include <stdio.h> #include <algorithm> #include <vector> #include <math.h> class Point {public:Point(int x, int y) : x_(x), y_(y) {}Point() : x_(0), y_(0) {}static bool OrderByX(const Point& left, const Point& right) {return left.x_ < right.x_;}static bool OrderByY(const Point& left, const Point& right) {return left.y_ < right.y_;}int x_;int y_; }; float Distance(const Point& left, const Point& right) {return sqrt(pow(left.x_ - right.x_, 2) + pow(left.y_ - right.y_, 2)); } int NearestPoints(const std::vector<Point>& points, int start, int end, Point* point1, Point* point2) {if (end > start) {int middle = (start + end) / 2;int left_min_distance = NearestPoints(points, start, middle, point1, point2);int right_min_distance = NearestPoints(points, middle + 1, end, point1, point2);int min_distance = left_min_distance > right_min_distance ? right_min_distance : left_min_distance;std::vector<Point> left_part_points;for (int i = start; i <= middle; ++i) {if (points[middle].x_ - points[i].x_ <= min_distance) {left_part_points.push_back(points[i]);}}sort(left_part_points.begin(), left_part_points.end(), Point::OrderByY);std::vector<Point> right_part_points;for (int i = middle + 1; i <= end; ++i) {if (points[i].x_ - points[middle].x_ <= min_distance) {right_part_points.push_back(points[i]);}}sort(right_part_points.begin(), right_part_points.end(), Point::OrderByY);int distance_y = 0;int point_distance = 0;for(int i = 0; i < left_part_points.size(); ++i) {for(int j = 0; j < right_part_points.size(); ++j) {distance_y = left_part_points[i].y_ > right_part_points[j].y_ ? left_part_points[i].y_ - right_part_points[j].y_ :right_part_points[j].y_ - left_part_points[i].y_;if (distance_y <= min_distance) {point_distance = Distance(left_part_points[i], right_part_points[j]);if (point_distance < min_distance) {min_distance = point_distance;*point1 = left_part_points[i];*point2 = right_part_points[j];}}}}return min_distance;} else {return 0x7FFFFFFF;} }int main(int argc, char** argv) {std::vector<Point> points;points.push_back(Point(2,3));points.push_back(Point(1,4));points.push_back(Point(3,0));points.push_back(Point(5,0));points.push_back(Point(5,1));sort(points.begin(), points.end(), Point::OrderByX);Point point1;Point point2;NearestPoints(points, 0, points.size() - 1, &point1, &point2);printf("Point1: (%d, %d) <--> Point2: (%d, %d)\n", point1.x_, point1.y_, point2.x_, point2.y_); }

總結(jié)

以上是生活随笔為你收集整理的寻找最近点对的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。