**問題描述：**

給定某空間中（直線空間或平面空間）n個點，請找出它們中的最近點對。你需要完成下列任務：

1、隨機產生或手工輸入n個點的坐標。

2、輸出最近的兩個點的坐標。

3、算法盡可能效率高。

解決方案：

針對問題，主要包括兩個方面的問題，一是在直線空間求最近點對，二是在平面空間求最近點對。具體解決辦法如下：

（1）直線空間求最近點對問題

求最近點對如果直接用蠻力法，即有n個點，從第一個點開始依次算出兩點直接的距離，進行大小比較，求出最小值，其時間效率為O（n^2）。那有沒有效率更高一點的辦法呢？結果當然是有的，那就是采用迭代法（時間效率為O(n*logn)，先找出一組點中的中間點，使得在中間點左邊的x坐標小于中間點x坐標，中間點右邊的x坐標大于中間點x坐標,分成左右兩組，用第一組左邊組X最大值與右邊組X最小值相減即得當前最短距離，在依次迭代，最后遞歸合并求出最終最短距離。

分治法方案具體代碼如下：

package com.liuzhen.ex_two;public class ClosestPionts {//初始化一個隨機數(shù)組public static int[] initializationArray(int n){int[] result = new int[n];for(int i = 0;i < n;i++)result[i] = (int)(Math.random()*1000); //采用隨機函數(shù)隨機生成1~1000之間的數(shù)return result;}//返回數(shù)組中最大值public static int getArrayMax(int a[] , int first , int end){int max = a[first];for(int i = first;i < end;i++){if(max < a[i])max = a[i];}return max;}//返回數(shù)組中最小值public static int getArrayMin(int a[] , int first , int end){int min = a[first];for(int i = first;i < end;i++){if(min > a[i])min = a[i];}return min;}//交換數(shù)組a[n]中兩個數(shù)的值public static void swapArray(int a[] , int i , int j){int temp = a[i];a[i] = a[j];a[j] = temp;}//采用分治法將數(shù)組a[n]分成兩組,滿足a[n1]<m,a[n2]>m(其中n1+n2 = n)public static int divideArray(int a[],int first,int end){int max = getArrayMax(a,first,end);int min = getArrayMin(a,first,end);double m = (max + min)/2.0;//System.out.println("分治法算出中位數(shù)m:"+m);int i = first , j = end-1;//int a1 = 0;for( ;i+1 <= j;){while(a[i] < m && i+1 <= j)i++; while(a[j] > m && i+1 <= j)j--;// a1++;// System.out.println("第"+a1+"此交換時a[i] = "+a[i]+" i = "+i+" a[j] = "+a[j]+" j = "+j);swapArray(a,i,j); //a[i]大于m的值與a[j]小于m的值進行交換，但數(shù)組的位置不變}//System.out.println("分組后，返回的序號j值是："+(j));return j;}//采用遞歸法合并最短距離值，返回最短距離的點public static int[] getMinDistancePoint(int a[] , int result[],int n ,int first , int end) {if(end-first <= 1){ //遞歸終止條件return result;}int j = divideArray(a,first,end);int minDistance = result[1] - result[0]; //最短距離兩點之間的距離大小if(minDistance > getArrayMin(a,j,end)-getArrayMax(a,first,j)){result[0] = getArrayMax(a,first,j); //最短距離兩點中數(shù)值最小的點result[1] = getArrayMin(a,j,end); //最短距離兩點中數(shù)值最小的點} int result_one[] = getMinDistancePoint(a,result,2,first,j); //遞歸int minDistance_one = result_one[1] - result_one[0]; int result_two[] = getMinDistancePoint(a,result,2,j,end); //遞歸int minDistance_two = result_two[1] - result_two[0];if(minDistance > minDistance_one)result = result_one;if(minDistance > minDistance_two)result = result_two;return result;}public static void main(String[] args){int a[] = new int[10];int b[] = new int[2];b[0] = 0;b[1] = 100;a = initializationArray(15);String one_text = "";for(int i = 0;i < 15;i++){one_text += "直線隨機點Point["+i+"] = "+a[i]+"\n";//System.out.print("數(shù)組a["+i+"] = "+a[i]+"\n");}int result[] = getMinDistancePoint(a,b,2,0,15);//System.out.println("result[0] = "+result[0]+"\n"+"result[1] = "+result[1]);one_text += "最短距離點對第1點result[0] = "+result[0]+"\n"+"最短距離點對第2點result[1] = "+result[1];System.out.print(one_text);} }

結果為

（2）平面空間求最近點對問題

平面空間教直線空間求最近點對問題就變得更加復雜一點，在此就只討論使用蠻力法求解平面空間求最近點對問題，如有對平面使用分治法求解感興趣的同學請看本文末尾參考資料2。

蠻力法方案具體如下：

由于是在平面，點坐標表示為（x,y）,在此先創(chuàng)建一個Point類(方便后續(xù)功能類實現(xiàn))：

package com.liuzhen.ex_two;public class Point {private int x; //平面點中的x坐標private int y; //平面點中的y坐標//未給類對象初始化時，默認點坐標為(0,0)public Point(){this.x = 0;this.y = 0;}public Point(int x,int y){this.x = x;this.y = y;}//給x賦值public void setX(int x){this.x = x;}//給y賦值public void setY(int y){this.y = y;}//返回xpublic int getX(){return x;}//返回ypublic int getY(){return y;} } 蠻力法 package com.liuzhen.ex_two;public class ClosestPionts {//平面中求兩點最短距離問題解法 //初始化一個平面中n個點，具體點的坐標值隨機生成public static Point[] initializationPlaneArray(int n){Point result[] = new Point[n];for(int i = 0;i < n;i++){int x1 = (int)(Math.random()*50); //采用隨機函數(shù)隨機生成1~100之間的數(shù)int y1 = (int)(Math.random()*50);result[i] = new Point(x1,y1); }return result;}//蠻力法直接求平面中兩點之間的最短距離，返回最短距離的兩點坐標public static Point[] getMinDistancePlanePoint(Point a[],int n){Point result[] = new Point[2];double min = 10000; //定義兩點之間最短距離變量，初始化為10000for(int i = 0;i < n;i++){int x = a[i].getX();int y = a[i].getY();for(int j = i+1;j < n;j++){int x1 = a[j].getX();int y1 = a[j].getY();long minSquare = (x-x1)^2 + (y-y1)^2; //利用數(shù)學中求兩點之間距離公式，得到兩點之間距離的平方double min1 = Math.sqrt(minSquare); //求兩點之間距離的中間變量if(min > min1){min = min1; result[0] = new Point(x,y);result[1] = new Point(x1,y1);}}}return result;}public static void main(String[] args){String two_text = "";Point c[] = initializationPlaneArray(15);for(int i = 0;i < 15;i++){two_text += "Point["+i+"] = "+"("+c[i].getX()+","+c[i].getY()+")"+"\n";//System.out.println("c["+i+"] = "+"("+c[i].getX()+","+c[i].getY()+")");}//System.out.println(two_text);Point back[] = getMinDistancePlanePoint(c,15);for(int i = 0;i < 2;i++){two_text += "距離最短的兩點第"+(i+1)+"個點坐標是："+"("+back[i].getX()+","+back[i].getY()+")"+"\n";//System.out.println("距離最短的兩點第"+(i+1)+"個點坐標是："+"("+back[i].getX()+","+//back[i].getY()+")");}System.out.println(two_text);}}

結果為

總結

以上是生活随笔為你收集整理的Java实现最近点问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。