ಇನ್ಸರ್ಟ್ ಪೊಸಿಷನ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಹುಡುಕಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಆಪಲ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್
ಅರೇ ಬೈನರಿ ಹುಡುಕಾಟ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ವಿಂಗಡಿಸಲಾಗಿದೆ ಸರಣಿ ಮತ್ತು ಗುರಿ ಪೂರ್ಣಾಂಕ. ನಾವು ಅದರ ಹುಡುಕಾಟ ಇನ್ಸರ್ಟ್ ಸ್ಥಾನವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ.

  1. ಗುರಿ ಮೌಲ್ಯವು ರಚನೆಯಲ್ಲಿದ್ದರೆ, ಅದರ ಸೂಚಿಯನ್ನು ಹಿಂತಿರುಗಿ.
  2. ಆದೇಶವನ್ನು ವಿಂಗಡಿಸಲು (ಕಡಿಮೆಯಾಗದ ರೀತಿಯಲ್ಲಿ) ಗುರಿಯನ್ನು ಸೇರಿಸಬೇಕಾದ ಸೂಚಿಯನ್ನು ಹಿಂತಿರುಗಿ.

ಉದಾಹರಣೆ

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

ವಿವರಣೆ

ಇನ್ಸರ್ಟ್ ಪೊಸಿಷನ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಗಳನ್ನು ಹುಡುಕಿ

ಅಪ್ರೋಚ್ (ಲೀನಿಯರ್ ಸರ್ಚ್)

ಗುರಿ ಮೌಲ್ಯವನ್ನು ಮೀರಿದ ಅಥವಾ ಸಮನಾಗಿರುವ ಮೊದಲ ಸೂಚಿಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಬಹುದು. ಪುರಾವೆ:

  • ಮೌಲ್ಯವು ಸಮನಾಗಿದ್ದರೆ, ಈ ಸೂಚ್ಯಂಕವು ಅಗತ್ಯವಾದ ಸೂಚ್ಯಂಕವಾಗಿದೆ.
  • ಇಲ್ಲದಿದ್ದರೆ ಈ ಸ್ಥಾನದಲ್ಲಿ ಟಾರ್ಗೆಟ್ ಸೇರಿಸಲಾಗುತ್ತಿತ್ತು.

ಕ್ರಮಾವಳಿ

  1. ಮೊದಲ ಸೂಚ್ಯಂಕದಿಂದ ರಚನೆಯ ಅಂತ್ಯದವರೆಗೆ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ
  2. If ರಚನೆ [i] ಗುರಿ ಮೌಲ್ಯವನ್ನು ಮೀರಿದೆ ಅಥವಾ ಸಮನಾಗಿರುತ್ತದೆ, ನಂತರ ನಾನು ಹಿಂತಿರುಗಿ
  3. ರಿಟರ್ನ್ n, ಅರೇ [ಸೂಚ್ಯಂಕ]> = ಗುರಿ ಮುಂತಾದ ಯಾವುದೇ ಸೂಚ್ಯಂಕವನ್ನು ನಾವು ಕಂಡುಕೊಂಡಿಲ್ಲ ಗುರಿ ಕೊನೆಯಲ್ಲಿ ಸೇರಿಸಬೇಕು
  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). ನಾವು ಅಸ್ಥಿರಗಳಿಗಾಗಿ ಸ್ಥಿರ ಜಾಗವನ್ನು ಬಳಸುತ್ತೇವೆ.

ಅಪ್ರೋಚ್ (ಬೈನರಿ ಸರ್ಚ್)

ರಚನೆಯನ್ನು ವಿಂಗಡಿಸಲಾಗಿದೆ. ಇದರಿಂದ ನಾವು ಮಾಡಬಹುದಾದ ಮೊದಲ ತೀರ್ಮಾನ: ಕೆಲವು ಸೂಚ್ಯಂಕದಲ್ಲಿನ ಮೌಲ್ಯ idx ಗುರಿಗಿಂತ ಕಡಿಮೆಯಾಗಿದೆ, ನಂತರ ಉಳಿದಿರುವ ಅಂಶಗಳನ್ನು ಪರಿಶೀಲಿಸುವ ಅಗತ್ಯವಿಲ್ಲ idx, ಅವು ಇನ್ನೂ ಚಿಕ್ಕದಾಗಿರುತ್ತವೆ. ಆದ್ದರಿಂದ ನಾವು a ಅನ್ನು ಬಳಸಬಹುದು ಬೈನರಿ ಹುಡುಕಾಟ ಹುಡುಕಾಟ ಇನ್ಸರ್ಟ್ ಸ್ಥಾನವನ್ನು ಕಂಡುಹಿಡಿಯಲು.

ಕ್ರಮಾವಳಿ

  1. ಒಂದು ರಚಿಸಿ ಬೈನರಿ ಸರ್ಚ್ () ಅಗತ್ಯವಿರುವ ಸೂಚಿಯನ್ನು ಹಿಂದಿರುಗಿಸುವ ಕಾರ್ಯ
  2. ಪ್ರಾರಂಭಿಸಿ ans = 0, ಇದು ಅಗತ್ಯ ಸೂಚ್ಯಂಕವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ
  3. ಎಡ ಮತ್ತು ಬಲ ಮಿತಿಗಳನ್ನು ಹೀಗೆ ಹೊಂದಿಸಿ 0 ಮತ್ತು ಎನ್ - 1 ಕ್ರಮವಾಗಿ, ರಚನೆಯ N = ಗಾತ್ರ
  4. ರವರೆಗೆ ಎಡ <= ಬಲ
    • ಈ ಮಿತಿಗಳ ಮಧ್ಯ ಸೂಚಿಯನ್ನು ಹುಡುಕಿ ಮಧ್ಯ = ಎಡ + ಬಲ / 2
    • If ಒಂದು [ಮಧ್ಯ] == ಗುರಿ, ಮಧ್ಯಕ್ಕೆ ಹಿಂತಿರುಗಿ
    • ಮೌಲ್ಯವು ಹೆಚ್ಚಿದ್ದರೆ, ನಾವು ಬಳಸಿ ಎಡ ಅರ್ಧಕ್ಕೆ ಹೋಗುತ್ತೇವೆ ಬಲ = ಮಧ್ಯ - 1 ಮತ್ತು ಉಳಿಸಿ ಉತ್ತರ = ಮಧ್ಯ
    • ಇದು ಯಾವಾಗ ಪ್ರಕರಣವನ್ನು ಬಿಡುತ್ತದೆ ಒಂದು [ಮಧ್ಯ] <ಗುರಿ, ನಾವು ಉಳಿಸುತ್ತೇವೆ ಉತ್ತರ = ಮಧ್ಯ + 1 ಮತ್ತು ಬಳಸಿ ಬಲ ಅರ್ಧಕ್ಕೆ ಸರಿಸಿ ಎಡ = ಮಧ್ಯ + 1
    • ಉತ್ತರಗಳನ್ನು ಹಿಂತಿರುಗಿ
  5. ಫಲಿತಾಂಶವನ್ನು ಮುದ್ರಿಸಿ

ಟಾರ್ಗೆಟ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಹುಡುಕಾಟ ಇನ್ಸರ್ಟ್ ಸ್ಥಾನವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಅಲ್ಗಾರಿದಮ್‌ನ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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). ಮತ್ತೆ, ನಾವು ಅಸ್ಥಿರಗಳಿಗಾಗಿ ಸ್ಥಿರ ಜಾಗವನ್ನು ಬಳಸುತ್ತೇವೆ.