[leetcode] 34. Find First and Last Position of Element in Sorted Array Medium
문제 설명
링크
배열에서 해당 원소의 첫번째 위치와 마지막 위치를 구하는 문제
접근 1 - bisect 이용
- python 의 bisect 모듈 이용
- 96% 빠르게 통과함!! 최고다!!
코드 1
def searchRange(self, nums: List[int], target: int) -> List[int]:
ans = []
idx = bisect.bisect_left(nums, target)
if idx < len(nums) and target == nums[idx]:
ans.append(idx)
else:
return [-1, -1]
idx = bisect.bisect_right(nums, target)
if idx > 0 and nums[idx - 1] == target:
ans.append(idx - 1)
return ans
접근 2 - 모듈 사용 X
- 왼쪽 한번
- 오른쪽 한번
- O(2logn) = O(logn)
코드 2
def searchRange(self, nums: List[int], target: int) -> List[int]:
ans = [-1, -1]
l, r = 0, len(nums) - 1
# left
while l <= r:
mid = ( l + r ) // 2
if nums[mid] == target:
if mid == 0 or mid > 0 and nums[mid - 1] != target:
ans[0] = mid
break
if nums[mid] >= target:
r = mid - 1
else:
l = mid + 1
l, r = 0, len(nums) - 1
while l <= r:
mid = ( l + r ) // 2
if nums[mid] == target:
if mid == len(nums) - 1 or mid < len(nums) - 1 and nums[mid + 1] != target:
ans[1] = mid
break
if nums[mid] > target:
r = mid - 1
else:
l = mid + 1
return ans
Author And Source
이 문제에 관하여([leetcode] 34. Find First and Last Position of Element in Sorted Array Medium), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@youn_22/leetcode-34.-Find-First-and-Last-Position-of-Element-in-Sorted-ArrayMedium저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)