सभी चुनौतियाँ
मध्यम 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

हर point की query तक Euclidean distance मापें, फिर distance के आधार पर points को rank करें, और tie होने पर smaller indices को पहले रखें।

संकेत 2

सिर्फ sorted points में से पहले k ही vote करते हैं, इसलिए final label training set के एक छोटे हिस्से पर depend करता है।

संकेत 3

अगर vote counts tie हों, तो उस label को चुनें जिसका nearest contributing point sorted neighbor list में सबसे पहले आता है।

अपेक्षित जटिलता

समय O(n log n), अतिरिक्त स्थान O(n)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

# कोडर भाषा समय मेमोरी AI रिव्यू समाधान
1 ННикита Python 930 ms - 5/5 कोड देखें

दूसरों से सीखें

समुदाय समाधान

स्पॉइलर अलर्ट: नीचे 1 पूरा समाधान पहले खुद हल करने की कोशिश करें। आप फिर भी अन्य डेवलपर्स का कोड और AI समीक्षा देख सकते हैं। चर्चा में शामिल होने के लिए साइन इन करें और चुनौती हल करें।