問題
k近傍法（KNN）は、新しい点に最も近い k 個の学習点を見て、最も多いラベルで分類します。
queryからすべての点までのユークリッド距離を計算します。- 点を距離順に並べます。距離が同じ場合は、インデックスが小さい点が先です。
- 先頭の k 個の点を取り、ラベルを数えます。
- 最も票の多いラベルを返します。同票の場合は、並べた順で最も近い点が先に来るラベルを返します。
knn_predict(points, labels, query, k) を実装してください。
入力
points: 学習点。各点は座標のリストです。
labels: 各点のラベル。
query: 分類する点。
k: 投票する近傍の数。
出力
予測したラベルを返してください。
制約
1 ≤ k ≤ 点の数 ≤ 1,000
1 ≤ 次元数 ≤ 20
-1,000 ≤ 各座標 ≤ 1,000
例
例 1
入力：
k = 3
query = [3.0, 3.0]
labels = ["A", "A", "B", "B"]
points = [
[1.0, 1.0],
[2.0, 2.0],
[8.0, 8.0],
[9.0, 9.0]
]
期待される出力：
expected = "A"入力：
long long k = 3;
std::vector<double> query = {3.0, 3.0};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{2.0, 2.0},
{8.0, 8.0},
{9.0, 9.0}
};
期待される出力：
std::string expected = "A";入力：
long k = 3;
double[] query = new double[] {3.0, 3.0};
string[] labels = new string[] {"A", "A", "B", "B"};
double[][] points = new double[][] {
new double[] {1.0, 1.0},
new double[] {2.0, 2.0},
new double[] {8.0, 8.0},
new double[] {9.0, 9.0}
};
期待される出力：
string expected = "A";解説
(3, 3) からの距離：(2, 2) ≈ 1.41、(1, 1) ≈ 2.83、(8, 8) ≈ 7.07。最も近い3つのラベルは A、A、B なので、答えは A です。
例 2
入力：
k = 2
query = [1.0, 1.0]
labels = ["red", "blue", "blue", "red"]
points = [
[0.0, 0.0],
[4.0, 0.0],
[0.0, 4.0],
[4.0, 4.0]
]
期待される出力：
expected = "red"入力：
long long k = 2;
std::vector<double> query = {1.0, 1.0};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<std::vector<double>> points = {
{0.0, 0.0},
{4.0, 0.0},
{0.0, 4.0},
{4.0, 4.0}
};
期待される出力：
std::string expected = "red";入力：
long k = 2;
double[] query = new double[] {1.0, 1.0};
string[] labels = new string[] {"red", "blue", "blue", "red"};
double[][] points = new double[][] {
new double[] {0.0, 0.0},
new double[] {4.0, 0.0},
new double[] {0.0, 4.0},
new double[] {4.0, 4.0}
};
期待される出力：
string expected = "red";解説
最も近い点は (0, 0)（red）です。次の2つ (4, 0) と (0, 4) は同じ距離なので、インデックスが小さい (4, 0)（blue）が選ばれます。red と blue が1票ずつで、red の点が先に来たので、答えは red です。
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。