जाँच गर्नुहोस् यदि एन र यसको डबल अवस्थित लेटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ गुगल
एरे

समस्या बयान

समस्यामा "N जाँच गर्नुहोस् कि N र त्यसको डबल अवस्थित छ" हामीलाई एन एलिमेन्ट्सको एरे दिइन्छ। एरे लम्बाई दुई भन्दा ठूलो वा बराबर छ।

हाम्रो कार्य भनेको एरेमा कुनै जोडी अवस्थित छ कि छैन भनेर जाँच्नु हो जुन पहिलो मान दोस्रो मान हो।

अधिक औपचारिक रूपमा हामीले जाँच गर्न आवश्यक छ कि त्यहाँ i, j छ जसको लागि म हुँ

उदाहरणका

arr = [7,1,14,11]
true

व्याख्या:

जाँच गर्नुहोस् यदि एन र यसको डबल अवस्थित लेटकोड समाधान

यस इनपुटको लागि आउटपुट सत्य हो किनकि प्रश्नले हामीलाई कुनै मान र दिइएको एर्रेमा यसको डबल एक्जिट जाँच गर्न सोध्छ, त्यसैले and र १ these यी मापदण्डलाई १ies भन्दा double भन्दा दोब्बर भयो।

जाँच गर्नुहोस् यदि एन र यसको डबल अवस्थित लेटकोड समाधानको लागि दृष्टिकोण

यस समस्या समाधान गर्न पहिलो दृष्टिकोण हो ब्रिट बल दृष्टिकोण एर्रेमा प्रत्येक एलिमेन्टको लागि, हामी पूर्ण एर्रे पार गर्नेछौं र जाँच गर्दछौं कि यो दोहोरो अवस्थित छ कि छैन। यदि हामीले यस सर्तलाई सन्तोष गर्ने तत्व भेट्टायौं भने हामी सत्यमा फर्किनेछौं, अन्यथा, हामी अन्त्यमा गलत फिर्ता हुनेछौं। यस दृष्टिकोणको लागि समय जटिलता O (n * n) हो किनकि एर्रेको प्रत्येक तत्वको लागि हामी पूर्ण एरेलाई ट्र्यावर्स गर्दैछौं।

हामी यो समस्यालाई बेहतर समयको जटिलतामा समाधान गर्न सक्दछौं अनअर्डर्ड नक्शा वा अनअर्डर गरिएको सेटको प्रयोग गरेर।

  1. एर्रे पार गर्नुहोस्।
  2. एर्रेमा प्रत्येक तत्वको लागि जाँच गर्नुहोस् कि यो डबल छ वा यसको आधा यो नक्सामा अवस्थित छ।
  3. यदि कन्डिसन सहि छ भने मात्र सहि फिर्ता गर्नुहोस् अन्यथा त्यो तत्वलाई नक्सामा जोड्नुहोस्।
  4. यदि एर्रे ट्राभर्सल गरियो र हामीले कुनै पनि तत्वको डबल फेला पारेनौं भने गलत फिर्ता गर्नुहोस्।

कार्यान्वयन

C ++ कोड जाँच गर्नुहोस् यदि N र यसको डबल अवस्थित छ

#include <bits/stdc++.h> 
using namespace std; 
    bool checkIfExist(vector<int>& arr) {
      unordered_map<int,bool>mp;
        for(int i=0;i<arr.size();i++)
        {
            if(mp[arr[i]*2]==1||(mp[arr[i]/2]==1&&arr[i]%2==0))
                return true;
            mp[arr[i]]=1;
        }
        return false;
    }
int main() 
{ 
 vector<int> arr = {7,1,14,11}; 
 bool ans=checkIfExist(arr);
 cout <<boolalpha;
 cout<<ans<<endl;
 return 0;
}
true

जाभा कोड जाँच गर्नुहोस् यदि एन र यसको डबल अवस्थित छ को लागी

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static boolean checkIfExist(int[] arr) {
        Set<Integer> seen = new HashSet<>();   
        for (int i : arr) {
            if (seen.contains(2 * i) || (i % 2 == 0 && seen.contains(i / 2)))
                return true;
            seen.add(i);
        }
        return false;
    }
  public static void main(String[] args) {
        int [] arr = {7,1,14,11}; 
        boolean ans=checkIfExist(arr); 
        System.out.println(ans);
  }
}
true

जटिलताको विश्लेषण यदि एन र यसको डबल अवस्थित लेटकोड समाधान

समय जटिलता

माथिको कोडको समय जटिलता हो ऊ) O (१) को रूपमा एक अनअर्डर गरिएको नक्शामा खोजी र सम्मिलितको औसत समय जटिलतालाई विचार गर्दै।

ठाउँ जटिलता

माथिको कोडको स्पेस जटिलता हो ऊ) किनभने नराम्रो अवस्थामा हामीलाई सबै तत्वहरू भण्डारण गर्न आवश्यक पर्दछ।

सन्दर्भ