โจทย์ทั้งหมด
ปานกลาง 1 ข้อที่แก้แล้ว อัตราผ่าน 100.0%

ตัวจำแนกแบบ K เพื่อนบ้านที่ใกล้ที่สุด

ทำนายป้ายกำกับด้วยเสียงข้างมากของจุดฝึก k จุดที่ใกล้ที่สุด

สิ่งที่คุณจะได้เรียนรู้

  • หาจุดฝึกที่ใกล้ที่สุด
  • ทำนายด้วยการโหวตเสียงข้างมาก
  • ตัดสินกรณีเสมอแบบกำหนดได้แน่นอน

โจทย์

K เพื่อนบ้านที่ใกล้ที่สุด (KNN) จำแนกจุดใหม่โดยดูจุดฝึก k จุดที่ใกล้ที่สุดแล้วเลือกป้ายกำกับที่พบบ่อยที่สุด

  1. คำนวณระยะทางแบบยุคลิดจาก query ไปยังทุกจุด
  2. เรียงจุดตามระยะทาง ถ้าระยะทางเท่ากัน จุดที่มีดัชนีน้อยกว่าจะมาก่อน
  3. เลือก k จุดแรกแล้วนับป้ายกำกับ
  4. คืนค่าป้ายกำกับที่ได้เสียงมากที่สุด ถ้าเสมอกัน ให้คืนค่าป้ายกำกับที่จุดซึ่งใกล้ที่สุดของมันมาก่อนในลำดับที่เรียงแล้ว

จงเขียน knn_predict(points, labels, query, k)

อินพุต

points: จุดฝึก แต่ละจุดเป็นลิสต์ของพิกัด

labels: ป้ายกำกับของแต่ละจุด

query: จุดที่ต้องการจำแนก

k: จำนวนเพื่อนบ้านที่ร่วมโหวต

เอาต์พุต

คืนค่าป้ายกำกับที่ทำนายได้

เงื่อนไข

1 ≤ k ≤ จำนวนจุด ≤ 1,000

1 ≤ จำนวนมิติ ≤ 20

-1,000 ≤ แต่ละพิกัด ≤ 1,000

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
points = [
    [1.0, 1.0],
    [2.0, 2.0],
    [8.0, 8.0],
    [9.0, 9.0]
]
labels = ["A", "A", "B", "B"]
query = [3.0, 3.0]
k = 3

ผลลัพธ์ที่คาดหวัง:
expected = "A"
อินพุต:
std::vector<std::vector<double>> points = {
    {1.0, 1.0},
    {2.0, 2.0},
    {8.0, 8.0},
    {9.0, 9.0}
};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<double> query = {3.0, 3.0};
long long k = 3;

ผลลัพธ์ที่คาดหวัง:
std::string expected = "A";
อินพุต:
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[] labels = new string[] {"A", "A", "B", "B"};
double[] query = new double[] {3.0, 3.0};
long k = 3;

ผลลัพธ์ที่คาดหวัง:
string expected = "A";

คำอธิบาย

ระยะทางจาก (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07 ป้ายกำกับ 3 อันที่ใกล้ที่สุดคือ A, A และ B ดังนั้นคำตอบคือ A

ตัวอย่างที่ 2
อินพุต:
points = [
    [0.0, 0.0],
    [4.0, 0.0],
    [0.0, 4.0],
    [4.0, 4.0]
]
labels = ["red", "blue", "blue", "red"]
query = [1.0, 1.0]
k = 2

ผลลัพธ์ที่คาดหวัง:
expected = "red"
อินพุต:
std::vector<std::vector<double>> points = {
    {0.0, 0.0},
    {4.0, 0.0},
    {0.0, 4.0},
    {4.0, 4.0}
};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<double> query = {1.0, 1.0};
long long k = 2;

ผลลัพธ์ที่คาดหวัง:
std::string expected = "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[] labels = new string[] {"red", "blue", "blue", "red"};
double[] query = new double[] {1.0, 1.0};
long k = 2;

ผลลัพธ์ที่คาดหวัง:
string expected = "red";

คำอธิบาย

จุดที่ใกล้ที่สุดคือ (0, 0) (red) อีกสองจุดถัดไปคือ (4, 0) และ (0, 4) อยู่ห่างเท่ากัน จึงเลือกจุดที่ดัชนีน้อยกว่าคือ (4, 0) (blue) red และ blue ได้คนละหนึ่งเสียง และจุดของ red มาก่อน ดังนั้นคำตอบคือ red

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

วัดระยะ Euclidean ของแต่ละจุดจาก query แล้วเรียงตามระยะ โดยให้ index ที่น้อยกว่าชนะเมื่อระยะเท่ากัน

คำใบ้ 2

ใช้แค่ k จุดแรกที่เรียงแล้วโหวต ดังนั้น label สุดท้ายจึงขึ้นกับชุดข้อมูลฝึกเพียงส่วนเล็กๆ

คำใบ้ 3

ถ้าคะแนนโหวตเสมอ ให้เลือก label ที่มีจุดใกล้ที่สุดที่เกี่ยวข้องและปรากฏก่อนในรายการเพื่อนบ้านที่เรียงแล้ว

ความซับซ้อนที่คาดหวัง

เวลา O(n log n), หน่วยความจำเพิ่ม O(n)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

# นักโค้ด ภาษา เวลา หน่วยความจำ คะแนนจาก AI คำตอบ
1 ННикита Python 930 ms - 5/5 ดูโค้ด

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

สปอยล์: มีคำตอบเต็ม 1 ข้อด้านล่าง ลองแก้ด้วยตัวเองก่อน คุณยังสามารถดูโค้ดของนักพัฒนาคนอื่นและรีวิว AI ได้ เข้าสู่ระบบและแก้โจทย์เพื่อร่วมพูดคุย