LeetCode - 정렬된 배열에서 요소의 첫 번째 및 마지막 위치 찾기

문제 설명

오름차순으로 정렬된 정수 nums의 배열이 주어지면,
주어진 대상 값의 시작 및 끝 위치를 찾습니다.

배열에서 대상을 찾을 수 없으면 [-1, -1]을 반환합니다.

문제 진술 출처: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array

예 1:

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

예 2:

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

예 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

설명

무차별 대입

무차별 접근 방식은 어레이의 선형 스캔을 수행하는 것입니다.
첫 번째 배열에서 시작하는 두 개의 포인터 leftIndex와 rightIndex를 사용합니다.
요소.

대상 요소의 첫 번째 항목이 발견되면
해당 인덱스를 leftIndex 변수에 할당합니다.
요소가 대상과 다를 때까지 계속 반복합니다.
현재 인덱스 - 1 값을 rightIndex에 할당합니다.

위 논리의 C++ 스니펫은 다음과 같습니다.

int firstIndex = -1, lastIndex = -1;
for (int i = 0; i < n; i++) {
    if (x != arr[i])
        continue;

    if (firstIndex == -1)
        firstIndex = i;
    lastIndex = i;
}

바이너리 검색 솔루션

이 문제에 대한 효율적인 해결책은 이진 검색을 사용하는 것입니다.
아래 알고리즘을 확인해 봅시다.

- set i = 0, j = nums.size() - 1
- set leftIndex and rightIndex to -1

- loop while i <= j
  - set mid = i + (j - i)/2

  - if nums[mid] > target
    - set j = mid - 1
  - else if nums[mid] < target
    - set i = mid + 1
  - else
    - leftIndex = mid
    - set j = mid - 1

- set i = 0, j = nums.size() - 1

- loop while i <= j
  - set mid = i + (j - i)/2

  - if nums[mid] > target
    - set j = mid - 1
  - else if nums[mid] < target
    - set i = mid + 1
  - else
    - rightIndex = mid
    - set i = mid + 1

- return [leftIndex, rightIndex]

위 접근법의 시간복잡도는 O(log(N))이며,
공간 복잡도는 O(1)입니다.


C++ 솔루션

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int i, j, mid;
        i = 0;
        j = nums.size() - 1;
        int leftIndex = -1, rightIndex = -1;

        while(i <= j){
            mid = (i + j)/2;
            if(nums[mid] > target){
                j = mid - 1;
            } else if (nums[mid] < target){
                i = mid + 1;
            } else {
                leftIndex = mid;
                j = mid - 1;
            }
        }

        i = 0; j = nums.size() - 1;
        while(i <= j){
            mid = (i + j)/2;
            if(nums[mid] > target){
                j = mid - 1;
            } else if (nums[mid] < target){
                i = mid + 1;
            } else {
                rightIndex = mid;
                i = mid + 1;
            }
        }

        vector<int> ans;
        ans.push_back(leftIndex);
        ans.push_back(rightIndex);

        return ans;
    }
};

골랑 솔루션

func searchRange(nums []int, target int) []int {
    i, j := 0, len(nums) - 1
    leftIndex, rightIndex := -1, -1

    for i <= j {
        mid := i + (j - i)/2

        if nums[mid] > target {
            j = mid - 1
        } else if nums[mid] < target {
            i = mid + 1
        } else {
            leftIndex = mid
            j = mid - 1
        }
    }

    i, j = 0, len(nums) - 1

    for i <= j {
        mid := i + (j - i)/2

        if nums[mid] > target {
            j = mid - 1
        } else if nums[mid] < target {
            i = mid + 1
        } else {
            rightIndex = mid
            i = mid + 1
        }
    }

    return []int{leftIndex, rightIndex}
}

자바스크립트 솔루션

var searchRange = function(nums, target) {
    let i = 0, j = nums.length - 1, mid;
    let leftIndex = -1, rightIndex = -1;

    while(i <= j){
        mid = ~~(i + (j - i) / 2);

        if(nums[mid] > target){
            j = mid - 1;
        } else if (nums[mid] < target){
            i = mid + 1;
        } else {
            leftIndex = mid;
            j = mid - 1;
        }
    }

    i = 0;
    j = nums.length - 1;

    while(i <= j){
        mid = ~~(i + (j - i) / 2);

        if(nums[mid] > target){
            j = mid - 1;
        } else if (nums[mid] < target){
            i = mid + 1;
        } else {
            rightIndex = mid;
            i = mid + 1;
        }
    }

    return [leftIndex, rightIndex];
};

솔루션이 어떻게 작동하는지 알아보기 위해 알고리즘을 시험 실행해 보겠습니다.

nums = [5, 7, 7, 8, 8, 10]
target = 8

Step 1: i = 0
        j = nums.size() - 1
          = 6 - 1
          = 5

Step 2: leftIndex = -1
        rightIndex = -1

Step 3: loop while i <= j
        0 <= 5
        mid = 2

        nums[2] > 8
        7 > 8
        false

        nums[2] < 8
        7 < 8
        true
        i = mid + 1
          = 3

Step 4: loop while i <= j
        3 <= 5
        mid = 4

        nums[4] > 8
        8 > 8
        false

        nums[4] < 8
        8 < 8
        false

        nums[4] == 8
        8 == 8
        true
        leftIndex = 4
        j = 4 - 1
          = 3

Step 5: loop while i <= j
        3 <= 3
        mid = 3

        nums[3] > 8
        8 > 8
        false

        nums[3] < 8
        8 < 8
        false

        nums[4] == 8
        8 == 8
        true
        leftIndex = 3
        j = 3 - 1
          = 2

Step 6: loop while i <= j
        3 <= 2
        false

Step 7: i = 0
        j = nums.size() - 1
          = 6 - 1
          = 5

Step 8: loop while i <= j
        0 <= 5
        mid = 2

        nums[2] > 8
        7 > 8
        false

        nums[2] < 8
        7 < 8
        true
        i = mid + 1
          = 3

Step 9: loop while i <= j
        3 <= 5
        mid = 4

        nums[4] > 8
        8 > 8
        false

        nums[4] < 8
        8 < 8
        false

        nums[4] == 8
        8 == 8
        true
        rightIndex = 4
        i = mid + 1
          = 5

Step 10: loop while i <= j
         5 <= 5
         mid = 5

         nums[5] > 8
         10 > 8
         true
         j = mid - 1
           = 5 - 1
           = 4

Step 11: loop while i <= j
         5 <= 4
         false

Step 12: return [3, 4]