खोज स्थिति Leetcode समाधान डालें


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना सेब ब्लूमबर्ग गूगल माइक्रोसॉफ्ट
ऐरे द्विआधारी खोज

इस समस्या में, हमें एक हल दिया जाता है सरणी और एक लक्ष्य पूर्णांक। हमें इसका Search Insert position खोजना होगा।

  1. यदि लक्ष्य मान सरणी में मौजूद है, तो इसका इंडेक्स वापस करें।
  2. उस सूचकांक को लौटाएं जिस पर आदेश को क्रमबद्ध रखने के लिए लक्ष्य को सम्मिलित किया जाना चाहिए (गैर-घटते तरीके से)।

उदाहरण

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

व्याख्या

सम्मिलित करें स्थिति Leetcode समाधान खोजें

दृष्टिकोण (रैखिक खोज)

हम पहले इंडेक्स का पता लगाने के लिए एक लूप चला सकते हैं जिसका मूल्य लक्ष्य मान से अधिक या बराबर है। सबूत:

  • यदि मान बराबर होता है, तो यह सूचकांक आवश्यक सूचकांक है।
  • इस स्थिति में लक्ष्य डाला गया होगा, अन्यथा।

कलन विधि

  1. सरणी के अंत में पहले सूचकांक से एक लूप चलाएं
  2. If सरणी [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

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

समय जटिलता

पर), जहां N = सरणी का आकार। सबसे खराब स्थिति में, हमें इसे जोड़ना होगा लक्ष्य सरणी के अंत में।

अंतरिक्ष की जटिलता

ओ (1)। हम चर के लिए निरंतर स्थान का उपयोग करते हैं।

दृष्टिकोण (द्विआधारी खोज)

सरणी को सॉर्ट किया गया है। पहला निष्कर्ष जो हम इससे बना सकते हैं, वह है: यदि किसी सूचकांक में मूल्य IDX लक्ष्य से कम है, तो उन तत्वों की जांच करने की कोई आवश्यकता नहीं है, जिन्हें छोड़ दिया गया है आईडीएक्स, क्योंकि वे और भी छोटे होंगे। तो हम एक का उपयोग कर सकते हैं द्विआधारी खोज खोज सम्मिलित स्थिति को खोजने के लिए।

कलन विधि

  1. बनाओ द्विआधारी खोज() फ़ंक्शन जो आवश्यक सूचकांक लौटाता है
  2. हस्ताक्षर करना उत्तर = 0, जो आवश्यक सूचकांक संग्रहीत करेगा
  3. बाईं और दाईं सीमा निर्धारित करें 0 और एन - 1 क्रमशः, सरणी का एन = आकार
  4. जब तक बाएँ <= दाएँ
    • इन सीमाओं का मध्य सूचकांक ज्ञात कीजिए mid = left + right / 2
    • If [a mid] == लक्ष्य, वापस मध्य में
    • यदि मूल्य अधिक है, तो हम प्रयोग करते हुए बाएं आधे भाग में चले जाते हैं दाहिना = मध्य - १ और बचाओ ans = मध्य
    • इस मामले को छोड़ देता है जब एक [मध्य] <लक्ष्य, हम बचाते हैं 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)। सबसे खराब स्थिति में, हम बना सकते हैं लॉगएन तुलना।

 अंतरिक्ष की जटिलता

हे (1)। फिर, हम चर के लिए निरंतर स्थान का उपयोग करते हैं।