সন্নিবেশ পজিশন লেটকোড সমাধান


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ গুগল মাইক্রোসফট
বিন্যাস বাইনারি অনুসন্ধান

এই সমস্যায়, আমাদের বাছাই করা হয় বিন্যাস এবং একটি লক্ষ্য পূর্ণসংখ্যা। আমাদের এটির অনুসন্ধান সন্নিবেশের অবস্থানটি আবিষ্কার করতে হবে।

  1. যদি লক্ষ্য মান অ্যারেতে উপস্থিত থাকে তবে তার সূচকটি ফেরত দিন।
  2. অর্ডারটি সাজানো (অ-হ্রাসমান পদ্ধতিতে) যাতে লক্ষ্য সন্নিবেশ করা উচিত সেই সূচকটি ফিরিয়ে দিন।

উদাহরণ

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

ব্যাখ্যা

সন্নিবেশ পজিশন লেটকোড সমাধানগুলি

পদ্ধতির (লিনিয়ার সন্ধান)

আমরা প্রথম সূচকটি খুঁজে পেতে একটি লুপ চালাতে পারি যার মান লক্ষ্যমাত্রার চেয়ে বেশি বা সমান। প্রুফ:

  • মান সমান হলে এই সূচকটি প্রয়োজনীয় সূচক।
  • অন্যথায় অন্যথায়, এই অবস্থানটিতে লক্ষ্য প্রবেশ করানো হত।

অ্যালগরিদম

  1. প্রথম সূচক থেকে অ্যারের শেষ পর্যন্ত একটি লুপ চালান
  2. If অ্যারে [আমি] লক্ষ্যমাত্রা ছাড়িয়ে যায় বা তার সমান হয়, তারপরে আমি ফিরে আসি
  3. প্রত্যাবর্তন n, যেমন অ্যারে [সূচী]> = লক্ষ্য হিসাবে আমরা কোনও সূচক পাই নি target লক্ষ্য শেষ পর্যন্ত .োকানো উচিত
  4. ফলাফল মুদ্রণ করুন

লক্ষ্য সন্ধানের সন্নিবেশ অবস্থানটি সন্ধান করতে অ্যালগরিদমের প্রয়োগ

সি ++ প্রোগ্রাম

#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)। আমরা ভেরিয়েবলের জন্য ধ্রুবক স্পেস ব্যবহার করি।

পদ্ধতির (বাইনারি অনুসন্ধান)

অ্যারে বাছাই করা হয়। আমরা এটি থেকে প্রথম উপসংহারটি তৈরি করতে পারি: যদি কোনও সূচকের মান হয় আইডিএক্স লক্ষ্যমাত্রার চেয়ে কম, তবে যে উপাদানগুলি রেখে গেছে তা পরীক্ষা করার দরকার নেই আইডিএক্স, তারা আরও ছোট হবে। সুতরাং আমরা একটি ব্যবহার করতে পারেন বাইনারি অনুসন্ধান অনুসন্ধান সন্নিবেশ অবস্থানটি সন্ধান করতে।

অ্যালগরিদম

  1. একটা তৈরি কর বাইনারি অনুসন্ধান () ফাংশন যা প্রয়োজনীয় সূচক ফেরত দেয়
  2. আরম্ভ উত্তর = 0, যা প্রয়োজনীয় সূচক সংরক্ষণ করবে
  3. বাম এবং ডান সীমা হিসাবে হিসাবে সেট করুন 0 এবং এন - 1 যথাক্রমে, অ্যারের N = আকার
  4. পর্যন্ত বাম <= ডান
    • এই সীমাগুলির মধ্য সূচকটি সন্ধান করুন মাঝ = বাম + ডান / 2
    • If একটি [মাঝারি] == লক্ষ্যমাঝখানে ফিরুন
    • মানটি আরও বেশি হলে, আমরা ব্যবহার করে বাম অর্ধে চলে যাই ডান = মাঝ - 1 এবং সংরক্ষণ করুন উত্তর = মাঝখানে
    • যখন কেস ছেড়ে যায় একটি [মাঝারি] <টার্গেট, আমরা বাঁচান উত্তর = মাঝ + 1 এবং ডান অর্ধেক ব্যবহার করে সরান বাম = মাঝ + 1
    • রিটার্ন উত্তর
  5. ফলাফল মুদ্রণ করুন

টার্গেট লেটকোড সমাধানের সন্ধান সন্নিবেশ অবস্থানটি সন্ধান করতে অ্যালগরিদমের প্রয়োগ Imp

সি ++ প্রোগ্রাম

#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

টার্গেট লেটকোড সমাধানের সন্ধান সন্নিবেশ করানোর জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (লগএন) সবচেয়ে খারাপ ক্ষেত্রে, আমরা করতে পারি লগএন তুলনা।

 স্থান জটিলতা

ও (1) আবার, আমরা ভেরিয়েবলের জন্য ধ্রুবক স্পেস ব্যবহার করি।