खोज सम्मिलित स्थिति लीटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल ब्लूमबर्ग गुगल माइक्रोसफ्ट
एरे बाइनरी खोज

यस समस्यामा हामीलाई क्रमबद्ध गरिएको छ array र एक लक्ष्य पूर्णांक। हामीले यसको खोज सम्मिलित स्थिति खोज्नुपर्नेछ।

  1. यदि लक्ष्य मान एर्रेमा उपस्थित छ भने, यसको अनुक्रमणिका फिर्ता गर्नुहोस्।
  2. अनुक्रमणिका फर्काउनुहोस् जुन लक्ष्य सम्मिलित हुनुपर्दछ ताकि अर्डरलाई क्रमबद्ध राख्नका लागि (न्यून हुँदैमा)।

उदाहरणका

1 2 3 4 5 
Target = 3
2
1 3 5 7 9
Target = 8
4

स्पष्टीकरण

खोज सम्मिलित स्थिति लीटकोड समाधानहरू

दृष्टिकोण (लिनियर खोज)

हामी पहिलो सूचकांक फेला पार्नको लागि एउटा लुप चलाउन सक्दछौं जसको मान लक्ष्य मान भन्दा बढि वा बराबर छ। प्रमाण:

  • यदि मान बराबर छ भने, तब यो सूचकांक आवश्यक अनुक्रमणिका हो।
  • लक्ष्य यस स्थितिमा सम्मिलित गरिएको थियो, अन्यथा।

अल्गोरिदम

  1. एरेको अन्त्यसम्म पहिलो अनुक्रमणिकाबाट एउटा लूप चलाउनुहोस्
  2. If एर्रे [i] लक्षित मान भन्दा बढि वा बराबर हुन्छ, त्यसपछि i फिर्ता गर्नुहोस्
  3. फिर्ती n, जस्तो कि हामीले कुनै अनुक्रमणिका भेट्टाएन जुन एरे [अनुक्रमणिका]> = लक्ष्य, त्यस्तै लक्ष्य अन्तमा घुसाउनु पर्छ
  4. परिणाम प्रिन्ट गर्नुहोस्

लक्ष्यको खोज सम्मिलित स्थिति फेला पार्न एल्गोरिथ्मको कार्यान्वयन

C ++ कार्यक्रम

#include <bits/stdc++.h>
using namespace std;

int searchInsert(vector<int>& a, int target)
{
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
    {
        if(a[i] >= target)
            return i;
    }
    return n;
}


int main()
{
    vector <int> a = {1 , 3 , 5 , 7 , 9};
    int target = 8;
    cout << searchInsert(a , target) << '\n';
}

जावा कार्यक्रम

class search_insert_position
{
    static int searchInsert(int[] a , int target)
    {
        int n = a.length;
        for(int i = 0 ; i < n ; i++)
        {
            if(a[i] >= target)
                return i;
        }
        return n;
    }

    public static void main(String args[])
    {
        int a[] = {1 , 3 , 5 , 7 , 9} , target = 8;
        System.out.println(searchInsert(a , target));
    }
}
4

खोजको लक्ष्य सम्मिलित स्थिति खोजीको जटिलता विश्लेषण

समय जटिलता

O (N), जहाँ N = एर्रेको आकार। सबैभन्दा नराम्रो अवस्थामा, हामीले यो थप्न आवश्यक छ लक्ष्य एर्रेको अन्त्यमा।

ठाउँ जटिलता

O (१)। हामी भ्यारीएबलका लागि स्थिर ठाउँ प्रयोग गर्छौं।

दृष्टिकोण (बाइनरी खोज)

एर्रे क्रमबद्ध छ। पहिलो निष्कर्ष जुन हामी योबाट बनाउन सक्छौं: यो यदि कुनै सूचकांकमा मान आईडीएक्स लक्ष्य भन्दा कम हो, त्यसोभए त्यहाँ छोडिएका तत्वहरू जाँच गर्न आवश्यक पर्दैन idx, तिनीहरू अझ सानो हुने थियो। त्यसैले हामी एक प्रयोग गर्न सक्छौं बाइनरी खोज खोज सम्मिलित स्थिति फेला पार्न।

अल्गोरिदम

  1. एक सिर्जना गर्नुहोस् बाइनरी खोज () प्रकार्य जसले आवश्यक अनुक्रमणिका फिर्ता गर्दछ
  2. आरम्भ गर्नुहोस् उत्तर = ०, जुन आवश्यक अनुक्रमणिका भण्डार गर्दछ
  3. बायाँ र दायाँ सीमाहरू यस रूपमा सेट गर्नुहोस् 0N - १ क्रमशः, एन = एर्रेको आकार
  4. सम्म बाँया <= दाँया
    • को रूपमा यी सीमाहरूको बीचको अनुक्रमणिका फेला पार्नुहोस् मध्य = बाँया + दाँया / २
    • If एक [मध्य] == लक्ष्यमध्य फिर्ता
    • यदि मान ठूलो छ भने, हामी प्रयोग गरेर बायाँ आधामा सर्छौं सही = मध्य - १ र सेभ गर्नुहोस् ANS = मध्य
    • यसले केस छोड्छ जब एक [मध्य] <लक्ष्य, हामी बचत गर्छौं ANS = मध्य + १ र सहि आधा प्रयोग गरेर सार्नुहोस् बाँया = मध्य + १
    • उत्तरहरू फर्काउनुहोस्
  5. परिणाम प्रिन्ट गर्नुहोस्

लक्ष्य लीटकोड समाधानको खोज सम्मिलित स्थिति खोजी गर्न एल्गोरिथ्मको कार्यान्वयन

C ++ कार्यक्रम

#include <bits/stdc++.h>
using namespace std;

int binarySearch(vector <int> &a , int target)
{
    int l = 0 , r = (int)a.size() - 1 , mid , ans = -1;
    while(l <= r)
    {
        mid = l + (r - l) / 2;
        if(a[mid] == target)
            return mid;
        if(a[mid] < target)
        {
            l = mid + 1;
            ans = mid + 1;
        }
        else
        {
            ans = mid;
            r = mid - 1;
        }
    }
    return ans;
}

int searchInsert(vector<int>& a, int target)
{
    return binarySearch(a , target);
}

int main()
{
    vector <int> a = {1 , 3 , 5 , 7 , 9};
    int target = 8;
    cout << searchInsert(a , target) << '\n';
}

जावा कार्यक्रम

class search_insert_position
{
    static int binarySearch(int[] a , int target)
    {
        int l = 0 , r = a.length - 1 , mid , ans = -1;
        while(l <= r)
        {
            mid = l + (r - l) / 2;
            if(a[mid] == target)
                return mid;
            if(a[mid] < target)
            {
                l = mid + 1;
                ans = mid + 1;
            }
            else
            {
                ans = mid;
                r = mid - 1;
            }
        }
        return ans;
    }

    static int searchInsert(int[] a , int target)
    {
        return binarySearch(a , target);
    }

    public static void main(String args[])
    {
        int a[] = {1 , 3 , 5 , 7 , 9} , target = 8;
        System.out.println(searchInsert(a , target));
    }
}
4

लक्ष्य लेटकोड समाधानको खोज सम्मिलित स्थिति खोज्नको जटिलता विश्लेषण

समय जटिलता

O (logN) सबैभन्दा नराम्रो अवस्थामा हामी बनाउन सक्छौं लग एन तुलना।

 ठाउँ जटिलता

O (१) फेरि हामी भ्यारीएबलका लागि स्थिर ठाउँ प्रयोग गर्छौं।