솔루션: 정렬된 배열에서 요소의 첫 번째 및 마지막 위치 찾기

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 누르거나 추천my solution post on Leetcode's forums 해주세요.

Leetcode 문제 #34(중간): 정렬된 배열에서 요소의 첫 번째 및 마지막 위치 찾기

설명:

(이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

예:

Example 1:
Input:	nums = [5,7,7,8,8,10], target = 8
Output:	[3,4]

Example 2:
Input:	nums = [5,7,7,8,8,10], target = 6
Output:	[-1,-1]

Example 3:
Input:	nums = [], target = 0
Output:	[-1,-1]

제약 조건:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non-decreasing array.
• -10^9 <= target <= 10^9

아이디어:

(이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

이 문제는 이진 검색의 정의에 가깝습니다. 이진 검색을 사용하면 정렬된 배열에서 대상 번호에 대한 삽입 인덱스를 찾을 수 있습니다. 각 단계에서 입력 배열을 절반으로 나누고 어느 절반이 숫자에 속하는지 결정하기 때문에 "이진"검색이라고 합니다. 이진 검색은 각 반복에서 나머지 배열의 절반을 제거할 수 있으므로 O(log N)의 시간 복잡도로 목적을 달성할 수 있습니다.

그러나 이 경우 우리는 목표 숫자(T)가 nums 배열(N)에서 어디에 위치할지 알아내고자 하는 것이 아니라 T가 실제로 N에 존재하는지 추가로 알아내고자 합니다. 시작 인덱스와 끝 인덱스.

이진 검색의 표준 구현은 T가 배치될 수 있는 가장 왼쪽 인덱스를 찾을 수 있지만 많은 언어에는 양쪽에 대한 기능이 있습니다. 그러나 여기서 두 세트의 함수를 정의하는 대신 약간의 창의성으로 단일 함수를 사용하여 답을 찾을 수 있습니다.

먼저 T에 대해 표준 왼쪽 이진 검색(찾기)을 수행할 수 있습니다. 다음으로 첫 번째 검색(N[Tleft])의 결과에 저장된 값을 확인하여 T가 N에 이미 존재하는지 쉽게 확인할 수 있습니다. 해당 인덱스에서 T를 찾지 못하면 T는 N에 존재하지 않으며 [-1, -1]을 반환해야 합니다.

그렇지 않으면 N에서 T 값 범위의 오른쪽 끝을 찾아야 합니다. 이렇게 하려면 find를 다시 사용할 수 있습니다. 이번에는 다음 정수(T + 1)와 함께 사용합니다. 이것은 T 값 범위의 끝 이후에 인덱스를 찾을 것이기 때문에 T 범위의 끝을 찾기 위해 한 위치 뒤로 이동할 수 있습니다.

이제 범위가 있으므로 반환할 수 있습니다.

시간 복잡도: 이진 검색의 경우 O(log N)

공간 복잡도: O(1)

구현:

Python에는 bisect_left() 및 bisect_right()의 양면에 대한 내장 이진 검색 기능이 있습니다.

Java용 내장 함수인 Arrays.binarySearch()는 가장 왼쪽에 있는 삽입 지점을 찾지 않으므로 자체 바이너리 검색 기능을 정의하는 것이 더 쉽습니다.

C++는 T 값 범위에 대한 반복자 포인터를 반환하는 내장 함수 equal_range()를 사용할 수 있습니다.

자바스크립트 코드:

(이동: Problem Description || Solution Idea )

var searchRange = function(N, T) {
    const find = (target, arr, left=0, right=arr.length) => {
        while (left <= right) {
            let mid = left + right >> 1
            if (arr[mid] < target) left = mid + 1
            else right = mid - 1
        }
        return left
    } 
    let Tleft = find(T, N)
    if (N[Tleft] !== T) return [-1,-1]
    return [Tleft, find(T+1, N, Tleft) - 1]
};

파이썬 코드:

(이동: Problem Description || Solution Idea )


w/bisect_left() 및 bisect_right():

class Solution:
    def searchRange(self, N: List[int], T: int) -> List[int]:
        Tleft = bisect_left(N, T)
        if Tleft == len(N) or N[Tleft] != T: return [-1, -1]
        return [Tleft, bisect_right(N, T) - 1]

w/사용자 정의 이진 검색:

class Solution:
    def searchRange(self, N: List[int], T: int) -> List[int]:
        def find(target, arr, left=0):
            right = len(arr) - 1
            while left <= right:
                mid = left + right >> 1
                if arr[mid] < target: left = mid + 1
                else: right = mid - 1
            return left
        Tleft = find(T, N)
        if Tleft == len(N) or N[Tleft] != T: return [-1, -1]
        return [Tleft, find(T+1, N, Tleft) - 1]

자바 코드:

(이동: Problem Description || Solution Idea )

class Solution {
    public int[] searchRange(int[] N, int T) {
        int Tleft = find(T, N, 0);
        if (Tleft == N.length || N[Tleft] != T) return new int[] {-1, -1};
        return new int[] {Tleft, find(T+1, N, Tleft) - 1};
    }
    public int find(int target, int[] arr, int left) {
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + right >> 1;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}

C++ 코드:

(이동: Problem Description || Solution Idea )


w/equal_range():

class Solution {
public:
    vector<int> searchRange(vector<int>& N, int T) {
        pair<vector<int>::iterator,vector<int>::iterator> range;
        range = equal_range(N.begin(), N.end(), T);
        int Tleft = distance(N.begin(), range.first);
        if (Tleft == N.size() || N[Tleft] != T) return {-1, -1};
        return {Tleft, (int)distance(N.begin(), range.second) - 1};
    }
};

w/사용자 정의 이진 검색:

class Solution {
public:
    vector<int> searchRange(vector<int>& N, int T) {
        int Tleft = find(T, N);
        if (Tleft == N.size() || N[Tleft] != T) return {-1, -1};
        return {Tleft, find(T+1, N, Tleft) - 1};
    }
    int find(int target, vector<int> arr, int left=0) {
        int right = arr.size() - 1;
        while (left <= right) {
            int mid = left + right >> 1;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
};