LeetCode - 34. Find First and Last Position of Element in Sorted Array (Python)

Medium, List 접근

RunTime : 66 ms / Memory : 17.68 MB

문제

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.

풀이

• 요구하는 데로 O(log n)의 시간복잡도를 가진 코드를 짜야했다.
• For문 한 번 도는걸로 해결하는 코드를 작성했다.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 0:
            return [-1, -1]
        if target not in nums:
            return [-1, -1]
        
        res = [0] * 2
        flag = False
        for idx in range(len(nums)):
            if flag == False and nums[idx] == target:
                res[0] = idx
                flag = True
                continue
            if flag and nums[idx] != target:
                res[1] = idx - 1
                break
        
        if flag and nums[-1] == target:
            res[1] = idx
        return res