मान लीजिए हमारे पास एक पूर्णांक ऐरे है; हमें सभी जोड़ियों में से k-वां सबसे छोटा दूरी ज्ञात करना है। एक जोड़ी (A, B) की दूरी वास्तव में A और B के बीच निरपेक्ष अंतर है। तो यदि इनपुट [1,3,8] जैसा है, तो सभी संभावित जोड़ियां [1,3], [3, 8], [1, 8] हैं, फिर जब k = 2, दूसरा सबसे छोटा दूरी 5 (8 - 3) है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
- n := nums का आकार, x := 0
- i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
- x := x और nums[i] का अधिकतम
- आकार x + 1 का एक ऐरे cnt परिभाषित करें
- i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
- j := i + 1 से प्रारंभ करें, जब j < n, j बढ़ाते हुए, करें -
- cnt[|nums[j] - nums[i]|] को 1 से बढ़ाएं
- j := i + 1 से प्रारंभ करें, जब j < n, j बढ़ाते हुए, करें -
- i := 0 से प्रारंभ करें, जब i <= x, i बढ़ाते हुए, करें -
- यदि cnt[i] >= k, तो -
- i वापस करें
- k := k - cnt[i]
- यदि cnt[i] >= k, तो -
- x वापस करें
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; class Solution { public: int smallestDistancePair(vector<int>& nums, int k) { int n = nums.size(); int x = 0; for(int i = 0; i < n; i++)x = max(x, nums[i]); vector <int> cnt(x + 1); for(int i = 0 ; i < n; i++){ for(int j = i + 1; j < n; j++){ cnt[abs(nums[j] - nums[i])]++; } } for(int i = 0; i <= x; i++){ if(cnt[i] >= k)return i; k -= cnt[i]; } return x; } }; main(){ Solution ob; vector<int> v = {1,3,8}; cout << (ob.smallestDistancePair(v, 2)); }इनपुट
{1,3,8}आउटपुट
5