Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में K-वां सबसे छोटा जोड़ी दूरी (Find K-th Smallest Pair Distance)


मान लीजिए हमारे पास एक पूर्णांक ऐरे है; हमें सभी जोड़ियों में से 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 से बढ़ाएं
  • i := 0 से प्रारंभ करें, जब i <= x, i बढ़ाते हुए, करें -
    • यदि cnt[i] >= k, तो -
      • i वापस करें
    • k := k - cnt[i]
  • 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

  1. C++ में BST में k-वां सबसे छोटा तत्व खोजें (BST में ऑर्डर स्टैटिस्टिक्स) C++ में BST में k-वां सबसे छोटा तत्व खोजें (BST में ऑर्डर स्टैटिस्टिक्स)

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री और एक मान K इनपुट के रूप में है, हमें ट्री में K-वां सबसे छोटा तत्व ढूंढना है।तो, यदि इनपुट इस तरह हैk = 3, तो आउटपुट 15 होगा।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −एक फ़ंक्शन find_kth_smallest() परिभाषित करें, यह रूट, काउंट, k लेगा,यदि रूट NULL है, त

  1. C++ में थ्रेशोल्ड दूरी पर सबसे कम पड़ोसियों वाला शहर ढूंढना C++ में थ्रेशोल्ड दूरी पर सबसे कम पड़ोसियों वाला शहर ढूंढना

    मान लीजिए n शहर हैं जो 0 से n-1 तक नंबरेड हैं। अगर हमारे पास ऐरे edges है जहां edges[i] = [fromi, toi, weighti] शहरों fromi और toi के बीच एक बाईडायरेक्शनल और वेटेड एज दर्शाता है, और दिया गया इंटीजर distanceThreshold है। हमें वह शहर ढूंढना है जिसमें उन शहरों की सबसे कम संख्या हो जो किसी पथ के माध्यम

  1. - C++ प्रोग्राम: सरणी में सबसे छोटे मान की आवृत्ति ज्ञात करना

    यहां हम देखेंगे कि सरणी में सबसे छोटे तत्व की आवृत्ति कैसे ज्ञात करें। मान लें सरणी तत्व [5, 3, 6, 9, 3, 7, 5, 8, 3, 12, 3, 10] हैं, यहां सबसे छोटा तत्व 3 है, और इस तत्व की आवृत्ति 4 है। इसलिए आउटपुट 4 है। इसे हल करने के लिए हम सूची का सबसे छोटा तत्व ज्ञात करेंगे, फिर पहले नंबर की घटनाओं को गिनेंगे