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

सी ++ में 3सम निकटतम


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

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

  • सरणी संख्याओं को क्रमबद्ध करें, उत्तर:=0, अंतर:=अनंत, n:=अंकों का आकार
  • मैं के लिए 0 से n - 1 की सीमा में
    • बाएं:=i + 1, दाएं:=n – 1
    • बाएं <दाएं
      • अस्थायी:=अंक [बाएं] + अंक [दाएं] + अंक [i]
      • अगर |लक्ष्य - अस्थायी|
      • यदि अस्थायी =लक्ष्य है, तो अस्थायी लौटाएं, अन्यथा जब अस्थायी> लक्ष्य, फिर 1 से दाएं घटाएं, अन्यथा 1 से बाएं बढ़ाएं
  • वापसी उत्तर

उदाहरण(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. सी ++ में एक उत्पाद सरणी पहेली (ओ (1) स्पेस)?

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

  1. सी ++ में संयोजन

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