719. K-वें सबसे छोटी जोड़ी की दूरी ज्ञात करें

कठिनाई: कठिन

विषय: ऐरे, दो पॉइंटर्स, बाइनरी सर्च, सॉर्टिंग

पूर्णांक a और b के युग्म की दूरी को a और b के बीच पूर्ण अंतर के रूप में परिभाषित किया गया है।

एक पूर्णांक सरणी अंक और एक पूर्णांक k दिया गया है, k^th सभी जोड़ों के बीच सबसे छोटी दूरी अंक[i] और अंक[j] लौटाएं जहां 0 .

उदाहरण 1:

• इनपुट: अंक = [1,3,1], के = 1
• आउटपुट: 0
• स्पष्टीकरण: यहां सभी जोड़े हैं:

  (1,3) -> 2
  (1,1) -> 0
  (3,1) -> 2

फिर 1^st सबसे छोटी दूरी वाली जोड़ी (1,1) है, और इसकी दूरी 0 है।

उदाहरण 2:

• इनपुट: अंक = [1,1,1], के = 2
• आउटपुट: 0

उदाहरण 3:

• इनपुट: अंक = [1,6,1], के = 3
• आउटपुट: 5

प्रतिबंध:

• n == अंक लंबाई
• 2 4
• 0 6
• 1

संकेत देना:

1. उत्तर के लिए बाइनरी खोज। आप कैसे जांच सकते हैं कि कितने जोड़ों में दूरी

समाधान:

हम बाइनरी सर्च और टू-पॉइंटर तकनीक के संयोजन का उपयोग कर सकते हैं। इस समस्या को हल करने के लिए चरण-दर-चरण दृष्टिकोण यहां दिया गया है:

दृष्टिकोण:

1. सरणी को क्रमबद्ध करें: सबसे पहले, सरणी संख्याओं को क्रमबद्ध करें। सॉर्टिंग किसी दिए गए मान से कम या उसके बराबर दूरी वाले जोड़ों की संख्या की कुशलतापूर्वक गणना करने में मदद करती है।

2. दूरी पर बाइनरी खोज: के-वें सबसे छोटी दूरी खोजने के लिए बाइनरी खोज का उपयोग करें। दूरियों के लिए खोज स्थान 0 (न्यूनतम संभव दूरी) से अधिकतम (संख्या) - न्यूनतम (संख्या) (सबसे बड़ी संभव दूरी) तक होता है।

3. दूरी वाले जोड़े गिनें ≤ मध्य: बाइनरी खोज में प्रत्येक मध्य मान के लिए, मध्य से कम या उसके बराबर दूरी वाले जोड़े की संख्या की गणना करें। यह दो-सूचक दृष्टिकोण का उपयोग करके कुशलतापूर्वक किया जा सकता है।

4. बाइनरी सर्च रेंज समायोजित करें: मध्य से कम या उसके बराबर दूरी वाले जोड़ों की संख्या के आधार पर, बाइनरी सर्च रेंज समायोजित करें। यदि गिनती k से कम है, तो निचली सीमा बढ़ाएँ; अन्यथा, ऊपरी सीमा घटाएँ।

आइए इस समाधान को PHP में लागू करें: 719। K-वें सबसे छोटी जोड़ी की दूरी ज्ञात करें

स्पष्टीकरण:

• countPairsWithDistanceLessThanOrEqualTo: यह फ़ंक्शन गिनता है कि कितने जोड़ों की दूरी मध्य से कम या उसके बराबर है। यह दो पॉइंटर्स का उपयोग करता है, जहां दायां वर्तमान तत्व है, और बाएं को तब तक समायोजित किया जाता है जब तक कि अंकों [दाएं] और अंकों [बाएं] के बीच का अंतर मध्य से कम या बराबर न हो जाए।

• smallestDistancePair: यह फ़ंक्शन k-th सबसे छोटी दूरी खोजने के लिए बाइनरी खोज का उपयोग करता है। निम्न और उच्च मान दूरियों के लिए वर्तमान खोज सीमा को परिभाषित करते हैं। मध्य मान को countPairsWithDistanceLessThanOrEqualTo फ़ंक्शन का उपयोग करके जांचा जाता है। परिणाम के आधार पर, खोज स्थान समायोजित किया जाता है।

यह एल्गोरिदम O(n log(max(nums) - min(nums)) n log n) की समय जटिलता के साथ k-th सबसे छोटी जोड़ी दूरी को कुशलता से ढूंढता है।

संपर्क लिंक

यदि आपको यह श्रृंखला उपयोगी लगी, तो कृपया रिपॉजिटरी को GitHub पर एक स्टार देने या पोस्ट को अपने पसंदीदा सोशल नेटवर्क पर साझा करने पर विचार करें। आपका समर्थन मेरे लिए बहुत मायने रखेगा!

यदि आप इस तरह की और अधिक उपयोगी सामग्री चाहते हैं, तो बेझिझक मुझे फ़ॉलो करें:

• लिंक्डइन
• गिटहब