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

C++ में 3Sum Closest समस्या


मान लीजिए हमारे पास n पूर्णांकों वाली एक सरणी nums और एक लक्ष्य है। हमें nums में तीन पूर्णांक ढूंढने हैं जिनका योग लक्ष्य के सबसे करीब हो। हम तीन पूर्णांकों का योग लौटाएंगे। हम यह मान ले सकते हैं कि प्रत्येक इनपुट का ठीक एक समाधान होगा। तो यदि दी गई सरणी [-1,2,1,-4] जैसी है और लक्ष्य 1 है, तो ट्रिपलेट [-1,2,1] होगा जिसका सबसे करीबी योग 2 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • सरणी nums को सॉर्ट करें, ans := 0, diff := Infinity, n := nums का आकार
  • i को 0 से n - 1 तक की रेंज में
    • left := i + 1, right := n - 1
    • जब तक left < right
      • temp := nums[left] + nums[right] + nums[i]
      • यदि |लक्ष्य - temp| < diff, तो ans := temp और diff := |लक्ष्य - temp|
      • यदि temp = लक्ष्य, तो temp लौटाएं, अन्यथा जब temp > लक्ष्य, तो right को 1 से घटाएं, अन्यथा left को 1 से बढ़ाएं
  • ans लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h> using namespace std; class Solution { public:    int threeSumClosest(vector<int>& nums, int target) {       sort(nums.begin(), nums.end());       int ans = 0;       int diff = INT_MAX;       int n = nums.size();       for(int i = 0; i < n; i++){          int left = i + 1;          int right = n - 1;          while(left < right){             int temp = nums[left] + nums[right] + nums[i];             if(abs(target - temp) < diff){                ans = temp;                diff = abs(target - temp);             }             if(temp == target)return temp;             else if(temp > target) right--;             else left++;          }       }       return ans;    } }; main(){    Solution ob;    vector<int> v = {-1,2,1,-4};    cout << ob.threeSumClosest(v, 1); }

इनपुट

[-1,2,1,-4] 1

आउटपुट

2

  1. - C++ में मूल बिंदु के निकटतम K बिंदु ढूंढना

    मान लीजिए हमारे पास बिंदुओं का एक समुच्चय है। हमारा कार्य K बिंदुओं को ढूंढना है जो मूल बिंदु के निकटतम हैं। मान लीजिए बिंदु (3, 3), (5, -1) और (-2, 4) हैं। तब निकटतम दो (K = 2) बिंदु (3, 3), (-2, 4) हैं।इस समस्या को हल करने के लिए, हम बिंदुओं की सूची को उनकी यूक्लिडियन दूरी के आधार पर सॉर्ट करेंगे,

  1. - C++ में प्रोडक्ट ऐरे पजल (O(1) स्पेस)

    यहां हम ऐरे से संबंधित एक रोचक समस्या देखेंगे। n तत्वों वाला एक ऐरे है। हमें n तत्वों का एक और ऐरे बनाना है। लेकिन दूसरे ऐरे का i-th स्थान पहले ऐरे के i-th तत्व को छोड़कर सभी तत्वों का गुणनफल रखेगा। और एक प्रतिबंध है कि हम इस समस्या में भाग ऑपरेटर का उपयोग नहीं कर सकते। हमें इस समस्या को इन-प्लेस हल

  1. - C++ में कॉम्बिनेशन्स

    मान लीजिए हमारे पास दो पूर्णांक n और k हैं। हमें 1 ... n में से k संख्याओं के सभी संभावित संयोजन ढूंढने हैं। इसलिए यदि n = 4 और k = 2, तो संयोजन [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] होंगे।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -हम इसे हल करने के लिए पुनरावर्ती फ़ंक्शन का उपयोग करेंगे। solve