검색 삽입 위치 Leetcode 솔루션


난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 구글 Microsoft
배열 이진 검색

이 문제에서 우리는 정렬 된 정렬 및 대상 정수. 검색 삽입 위치를 찾아야합니다.

  1. 대상 값이 배열에 있으면 해당 인덱스를 반환합니다.
  2. 정렬 된 순서를 유지하기 위해 타겟이 삽입되어야하는 인덱스를 반환합니다 (비 감소 방식).

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

설명

검색 삽입 위치 Leetcode 솔루션

접근 (선형 검색)

루프를 실행하여 값이 목표 값보다 크거나 같은 첫 번째 인덱스를 찾을 수 있습니다. 증명:

  • 값이 같으면이 색인이 필수 색인입니다.
  • 그렇지 않으면 타겟이이 위치에 삽입되었을 것입니다.

암호알고리즘

  1. 첫 번째 인덱스에서 배열 끝까지 루프 실행
  2. If 배열 [i] 목표 값보다 크거나 같으면 i를 반환합니다.
  3. 반환 n, array [index]> = target과 같은 인덱스가 없으므로 목표 끝에 삽입해야합니다
  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 = 배열의 크기입니다. 최악의 경우에는 목표 배열의 끝에.

공간 복잡성

O (1). 변수에 상수 공간을 사용합니다.

접근 방식 (바이너리 검색)

배열이 정렬됩니다. 이로부터 얻을 수있는 첫 번째 결론은 다음과 같습니다. idx 목표보다 작 으면 남은 요소를 확인할 필요가 없습니다. idx, 더 작아 질 것입니다. 그래서 우리는 이진 검색 검색 삽입 위치를 찾으십시오.

암호알고리즘

  1. 만들기 binarySearch () 필요한 인덱스를 반환하는 함수
  2. 초기화 ans = 0, 필요한 색인을 저장할
  3. 왼쪽 및 오른쪽 제한 설정 0N – 1 각각 N = 배열의 크기
  4. 까지 왼쪽 <= 오른쪽
    • 이 한계의 중간 지수를 다음과 같이 찾으십시오. 중간 = 왼쪽 + 오른쪽 / 2
    • If a [mid] == 타겟, 중간 반환
    • 값이 더 큰 경우 사용하여 왼쪽 절반으로 이동합니다. 오른쪽 = 중간 – 1 저장 = 중간
    • 이것은 경우를 떠난다 a [mid] <타겟, 우리는 저장 = 중간 + 1 다음을 사용하여 오른쪽으로 이동합니다. 왼쪽 = 중간 + 1
    • 반환 ans
  5. 결과 인쇄

대상 Leetcode 솔루션의 검색 삽입 위치를 찾는 알고리즘 구현

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

대상 Leetcode 솔루션의 검색 삽입 위치 찾기의 복잡성 분석

시간 복잡성

O (logN). 최악의 경우 logN 비교.

 공간 복잡성

O (1). 다시 말하지만, 변수에 대해 상수 공간을 사용합니다.