엔지니어 게시판
LeetCode 솔루션 분류

[7/25] 34. 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
Accepted
1,181,725
Submissions
2,917,893

관련자료

댓글 1

학부유학생님의 댓글

  • 학부유학생
  • 작성일
Runtime: 136 ms, faster than 44.59% of Python3 online submissions for Find First and Last Position of Element in Sorted Array.
Memory Usage: 15.5 MB, less than 10.25% of Python3 online submissions for Find First and Last Position of Element in Sorted Array.
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        
        l, r = 0, len(nums)-1

        while l<=r:
            mid = (l+r)//2
            
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        
        left = l
        l, r = 0, len(nums)-1
        
        while l <= r:
            mid = (l+r)//2
            
            if nums[mid] > target: 
                r = mid - 1
            else:
                l = mid + 1
        
        return [left, r] if left<=r else [-1,-1]
            
전체 240 / 1 페이지
게시글 쓰기
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 75 명
  • 오늘 방문자 742 명
  • 어제 방문자 1,117 명
  • 최대 방문자 1,463 명
  • 전체 회원수 378 명
알림 0