在2D平面K近鄰

查找K個最接近點在二維平面上的原點，給出含N百分點。輸出必須在非陣列降序。

解決方案：我已經解決了這個使用比較和優先級隊列和我的代碼看起來像下面：

class Point { 
    double x; 
    double y; 

    public Point(double x, double y) { 
     this.x = x; 
     this.y = y; 
    } 
} 

public class KClosestPoints { 
    public Point[] getKNearestPoints(Point[] points, int k) { 
     if (k == 0 || points.length == 0) { 
      return new Point[0]; 
     } 
     Point[] rValue = new Point[k]; 
     int index = k - 1; 
     if (points.length < k) { 
      index = points.length - 1; 
     } 
     final Point org = new Point(0, 0); 
     PriorityQueue<Point> pq = new PriorityQueue<Point>(k, 
       new Comparator<Point>() { 
        @Override 
        public int compare(Point o1, Point o2) { 
        Double d2 = getDistance(o2, org); 
        Double d1 = getDistance(o1, org); 
        if (d2 > d1) { 
         return 1; 
        } else if (d2 < d1) { 
         return -1; 
        } else 
         return 0; 
       } 
       }); 
     for (int i = 0; i < points.length; i++) { 
      pq.offer(points[i]); 
      if (pq.size() > k) { 
       pq.poll(); 
      } 
     } 
     while (!pq.isEmpty()) { 
      rValue[index] = pq.poll(); 
      index--; 
     } 
     return rValue; 
    } 

    private static double getDistance(Point a, Point b) { 
     return Math.sqrt(((a.x - b.x) * (a.x - b.x)) 
       + ((a.y - b.y) * (a.y - b.y))); 
    }

我的代碼適用於所有的測試情況下，我已經使用，除了這一點：

test6[0] = new Point(Double.MIN_VALUE, Double.MAX_VALUE); 
test6[1] = new Point(Double.MIN_VALUE, Double.MIN_VALUE); 
test6[2] = new Point(Double.MAX_VALUE, Double.MAX_VALUE); 
getKNearestPoints(test6, 2);

答案應該是test6 [0]和test6 [1]，而這段代碼的答案是test6 [0]和test6 [2]。幫助我找到問題。

編輯：後來我已經注意到它在所有的測試案例，其中k給出錯誤的答案= 2時的點是積極的和消極的，一個這樣的試驗情況進行了

來源

2016-12-29 ojas

那麼，什麼是'Double.MIN_VALUE - Double.MIN_VALUE'在Java中？順便說一下，是否有一個原因，你爲什麼使用優先級隊列，而不是按距離原點排序點並返回它們的第一個「k」？ – 2016-12-29 20:11:37

我可以沒有優先級隊列。然後，我必須計算每個點與原點之間的距離，然後對距離進行排序並獲取前k個距離。距離可以使用散列圖映射到點。我只是想保存內存，而不是採用hashmap。這兩種情況下的複雜性將是O（n logn） – ojas

我想通過treeMap解決方案雖然 – ojas

提到的問題，您都在問，有一個問題計算距離：

Point # 0 = (0, 0) 
Point # 1 = (Double.MIN_VALUE, Double.MAX_VALUE) -> (4.9E-324, 1.7E308) 
Point # 2 = (Double.MIN_VALUE, Double.MIN_VALUE) -> (4.9E-324, 4.9E-324) 
Point # 3 = (Double.MAX_VALUE, Double.MAX_VALUE) -> (1.7E308, 1.7E308)

注：Double.MIN_VALUE爲正數。

現在的歐氏距離d = Math.sqrt(((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y)));回報Infinity當計算Point # 0和Point # 1，並Point # 0和Point # 3之間的距離，這是因爲：

點＃1

(a.x - b.x) * (a.x - b.x) = (1.7E308 - 0) * (1.7E308 - 0) = 1.7E308 * 1.7E308 = Infinity 
Math.sqrt(Infinity + Infinity) = Infinity;

得到的Point # 1的距離後Point # 0（Infinity），然後將其與的距離進行比較和Point # 0（另外Infinity）則Infinity = Infinity是true，因此Comparator表示「兩點都相等」，並且PriorityQueue不按您的意願排序。

對於Double.MAX_VALUE操作則不得使用Double，而是使用BigDecimal：

private BigDecimal getDistance(Point a, Point b) { 
    BigDecimal dx = BigDecimal.valueOf(a.x - b.x); 
    BigDecimal dy = BigDecimal.valueOf(a.y - b.y); 
    BigDecimal distance = dx.pow(2).add(dy.pow(2)); 
    return distance; 
}

爲什麼我們不計算與平方根的實際距離？因爲：

BigDecimal類沒有這樣的方法（如果你可以使用here）。
因爲如果a > b然後sqrt(a) > sqrt(b)，它的比例，所以它足夠得到沒有應用平方根函數的值。

趁着BigDecimal，它實現了自己的Comparator所以我們用它在Comparator的compareTo方法定義：

@Override 
public int compare(Point o1, Point o2) { 
    BigDecimal d1 = getDistance(o1); 
    BigDecimal d2 = getDistance(o2); 
    return d1.compareTo(d2); 
}

來源

2016-12-29 22:05:55

在2D平面K近鄰

回答

相關問題