Zayden

leetcode - Find First and Last Position of Element in Sorted Array

July 29, 2023

문제 설명

감소하지 않는 순서로 정렬된 정수 배열이 주어졌을 때, 주어진 목표 값의 시작과 끝 위치를 구합니다.

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

런타임 복잡도가 O(log n)인 알고리즘을 작성해야 합니다.

  • 예시 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 <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109

문제 접근

투 포인터를 사용하여 left 는 배열의 첫 인덱스 부터 right 는 배열의 끝 인덱스 부터 하나씩 찾으면서 진행합니다.

  1. left, right 각각 변수를 선언하여 각 index 위치를 할당합니다.
  2. left는 1을 더하면서 right는 1을 빼면서 위치를 변경하여 target을 찾습니다.
  3. 위 과정을 left 와 right 의 위치가 만날때까지 반복합니다.
function solution(nums, target) {
  if (nums.length === 0) {
    return [-1, -1];
  }

  let left = 0;
  let right = nums.length - 1;

  while(left <= right) {
    if (nums[left] === target && nums[right] === target) {
      return [left, right];
    }

    if (nums[left] !== target) {
      left++;
    }

    if (nums[right] !== target) {
      right--;
    }
  }

  return [-1, -1];
};