[Leetcode/파이썬] 34. Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array

---

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

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

You must 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]

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        ans = []
        for i in range(len(nums)) :
            if nums[i] == target :
                ans.append(i)

        return [min(ans), max(ans)] if ans else [-1, -1]

이건 딱히 뭐라해야될지 모르겠다. 그냥 문제를 읽고 문제에 적힌 대로 풀었는데 풀렸다.

문제에서 주어진 정렬된 배열 (오름차순) target 에 해당하는 배열의 처음과 끝 인덱스를 가져와라.

return 부분에서 가장 처음 등장하는 인덱스와 가장 마지막에 등장하는 인덱스를 return 하고 만약 ans 배열에 아무런 숫자가 존재하지 않는다면 [-1, -1]을 리턴하라는 조건문만 잘 작성해준다면 문제없이 해결될 것이다.

-----------수정

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums)==0:
            return [-1,-1]
        
        idx = self.binary_search(nums, target)

        if idx == -1 :
            return [-1, -1]
        
        return self.two_pointer(nums, target, idx)

    def binary_search(self, nums, target) :
        left, right = 0, len(nums) - 1

        while left <= right :
            mid = (left + right) // 2
            
            if target == nums[mid] :
                return mid  
            elif target > nums[mid] :
                left = mid + 1
            else :
                right = mid - 1
        
        return -1

    def two_pointer(self, nums, target, idx) :
        left, right = idx, idx

        while 0 <= left and nums[left] == target :
            left -= 1
        left += 1

        while right <= len(nums) - 1 and nums[right] == target :
            right += 1
        right -= 1

        return [left, right]

문제 가장 위에 반드시 log n 의 시간복잡도로 해결하라는 문구를 못보았다. 문제 해결은 이전 코드도 가능하나 그래도 정석적인 풀이 역시 배워간다는 의미에서 수정을 한다. 이 코드는 다른 분 코드를 참고하였다.

기본적은 이진탐색 에서 살짝 변형이 이루어지긴 하였지만 크게 이루어지진 않았다.