973-原点に最も近いK点
前言
Weekly Contest 119の原点に最も近いK点:
平面上の点からなるリスト
△ここで、平面上の2点間の距離はユークリッド距離です.
任意の順序で答えを返すことができます.ポイント座標の順序を除いて、答えは一意であることを確認します.
例1:
例2:
ヒント:
問題を解く構想.
本題はまずユークリッド距離とは何かを知ることです.ユークリッド距離はユークリッドメトリックとも呼ばれ、ユークリッド空間における2点間の「普通」(すなわち直線)距離を指す.概念を説明するのは難しいが、本題で用いる2次元空間でユークリッド距離を計算する数学式を用いるとよく理解できる.既知の原点座標は
$$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} $$
点Aから原点までのユークリッド距離は
$$\sqrt{x_1^2+y_1^2} $$
次に,この式を用いて各点から原点までのユークリッド距離を計算することができ,その後,最近のいくつかの点を見つけるだけでよい.ここでは、タイトルの
ポイント座標の順序を除いて、答えは一意であることを確認します.
これは、各点から原点までの例が異なるべきであることを示しています.
インプリメンテーションコード
Weekly Contest 119の原点に最も近いK点:
平面上の点からなるリスト
points
があります.K
個の原点(0, 0)
に最も近い点を見つける必要がある.△ここで、平面上の2点間の距離はユークリッド距離です.
任意の順序で答えを返すことができます.ポイント座標の順序を除いて、答えは一意であることを確認します.
例1:
:points = [[1,3],[-2,2]], K = 1
:[[-2,2]]
:
(1, 3) sqrt(10),
(-2, 2) sqrt(8),
sqrt(8) < sqrt(10),(-2, 2) 。
K = 1 , [[-2,2]]。
例2:
:points = [[3,3],[5,-1],[-2,4]], K = 2
:[[3,3],[-2,4]]
( [[-2,4],[3,3]] 。)
ヒント:
1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][3] < 10000
問題を解く構想.
本題はまずユークリッド距離とは何かを知ることです.ユークリッド距離はユークリッドメトリックとも呼ばれ、ユークリッド空間における2点間の「普通」(すなわち直線)距離を指す.概念を説明するのは難しいが、本題で用いる2次元空間でユークリッド距離を計算する数学式を用いるとよく理解できる.既知の原点座標は
(0,0)
であり、2つの点A (x1,y1)
とB (x2,y2)
に存在し、点AとBのユークリッド距離は$$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} $$
点Aから原点までのユークリッド距離は
$$\sqrt{x_1^2+y_1^2} $$
次に,この式を用いて各点から原点までのユークリッド距離を計算することができ,その後,最近のいくつかの点を見つけるだけでよい.ここでは、タイトルの
ポイント座標の順序を除いて、答えは一意であることを確認します.
これは、各点から原点までの例が異なるべきであることを示しています.
インプリメンテーションコード
/**
* 973. K
*
* @param points
* @param K
* @return
*/
public int[][] kClosest(int[][] points, int K) {
// , , key
//Map TreeMap TreeMap key ( )
Map map=new TreeMap<>();
for (int i=0;i> it=map.entrySet().iterator();
// ,
int index=0;
while (it.hasNext()){
int[] point=it.next().getValue();
result[index]=point;
if(index+1==K){
break;
}else{
++index;
}
}
return result;
}