Издөө Insert Position Leetcode Solution  


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon алма Bloomberg Гугл Microsoft
Алгоритмы согуштук тизме Binary Search коддоо интервью интервью даярдоо LeetCode LeetCodeSolutions

Бул көйгөйдө, бизге иреттелген берилет согуштук тизме жана максаттуу бүтүн сан. Биз анын Издөө Кыстаруу Позициясын табышыбыз керек.

  1. Эгерде максаттуу маани массивде болсо, анын индексин кайтарыңыз.
  2. Буйрутманы иреттеп туруу үчүн (азайбаса), бутага киргизиле турган индексти кайтарыңыз.

мисал  

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

түшүндүрүү

Издөө Insert Position Leetcode Solutionsтөөнөч

Ыкма (Сызыктуу Издөө)  

Биз маани максаттуу көрсөткүчтөн ашкан же барабар болгон биринчи индексти табуу үчүн цикл иштете алабыз. Далил:

  • Эгер маани барабар болсо, анда бул индекс талап кылынган индекс болуп саналат.
  • Максат ушул позицияга киргизилген болмок, антпесе.

Algorithm

  1. Биринчи индекстен массивдин аягына чейин цикл иштетүү
  2. If массив [i] максаттуу мааниден ашып кетсе же барабар болсо, анда i
  3. кайра n, [indeks]> = максаттуу массивдин көрсөткүчүн таппаганыбыздай, демек бута аягында киргизилиши керек
  4. Жыйынтыгын басып чыгарыңыз

Максаттын Издөө Insert Position табуу алгоритмин ишке ашыруу

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';
}

Java программасы

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 = массивдин көлөмү. Эң начар учурда, биз тиркөөбүз керек бута массивдин аягында

ошондой эле
Чектик Leetcode Чечими берилген эң кичинекей бөлгүчтү табыңыз

Космостун татаалдыгы

O (1). Биз өзгөрүлмө үчүн туруктуу мейкиндикти колдонобуз.

Ыкма (Бинардык издөө)  

Массив иреттелген. Мындан чыгара турган биринчи тыянак: Эгерде кандайдыр бир индекстеги маани idx максаттуу көрсөткүчтөн аз болсо, анда калган элементтерди текшерүүнүн кажети жок idx, анткени алар андан да кичинекей болмок. Ошентип, биз колдоно алабыз Binary Search Search Insert Position табуу.

Algorithm

  1. түзүү binarySearch () керектүү индексти кайтаруучу функция
  2. Initialize ans = 0, керектүү индекси сакталат
  3. Сол жана оң чектерин катары коюңуз жана N - 1 тиешелүүлүгүнө жараша, N = массивдин көлөмү
  4. чейин сол <= оң
    • Катары ушул чектердин орточо индексин табыңыз орто = сол + оң / 2
    • If a [mid] == максаттуу, ортосуна кайтып келүү
    • Мааниси чоңураак болгон учурда, колдонуп сол жарымына өтөбүз оң = ортосу - 1 жана сактоо лет = орто
    • Бул ишти качан калтырат a [mid] <target, биз үнөмдөйбүз лет = орто + 1 жана колдонуп оң жарымына жылыңыз сол = орто + 1
    • Кайтып келүү
  5. Жыйынтыгын басып чыгарыңыз

Target Leetcode Solution издөө Insert Position табуу алгоритмин ишке ашыруу

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';
}

Java программасы

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

Максаттуу Leetcode Solution издөө кыстаруу ордун табуунун татаалдыгын талдоо

Убакыт татаалдыгы

O (logN). Эң начар учурда биз жасай алабыз logN салыштыруу.

ошондой эле
Эки дарактын Leetcode чечиминин минималдуу тереңдиги

 Космостун татаалдыгы

O (1). Дагы, биз өзгөрүлмө үчүн туруктуу мейкиндикти колдонушат.