1 분 소요

문제

Account Login - LeetCode

  • 오름차순 정렬된 배열 nums가 주어졌을때
  • k번째로 없는 숫자를 반환해라

접근 방식

  • idx까지 몇 개의 missing number가 있는지 반환하는 함수 missing(idx)를 정의한다. missing = lambda idx: nums[idx] - nums[0] - idx

  • missing(idx-1) < k ≤ missing(idx)를 만족하는 idx를 찾는다 ⇒ Parametric binarySearch
  • 정답을 리턴한다. (k번 째 missing number)
    • kth missing = nums[idx-1] + (k - missing(idx-1))

알아야할 개념

  • parametric binary search

  • lower bound : 찾고자 하는 값 이상이 처음 나타나는 위치를 찾음

      '''
  lowerbound
  : (배열에 같은 원소가 여러 개 있을 경우) 찾고자 하는 값 이상이 처음 나타나는 위치
  [문제 예시]
  n개로 이루어진 정수 집합에서 k 이상인 수가 처음으로 등장하는 위치를 찾으시오.
  단, 입력되는 집합은 오름차순으로 정렬되어 있으며 (이분탐색 가능), 같은 수가 여러 개 존재할 수 있다.
  '''
    
  def lowerbound(arr, key):
      # arr은 정렬되어있다고 가정
      lo, hi = 0, len(arr)-1
      while lo<hi:
          mid = (lo+hi)//2
          if arr[mid] < key:
              lo = mid+1
          else:
              hi = mid
      # while이 끝날때까지 돈다. 도중에 key랑 같으면 return 같은거 안함. -> 당연
      return lo

solution

def missingElement(nums: List[int], k: int) -> int:
    # Return how many numbers are missing until nums[idx]
    missing = lambda idx: nums[idx] - nums[0] - idx

    n = len(nums)
    # edge case : If kth missing number is larger than the last element of the array
    if k > missing(n-1):
        return nums[-1] + k - missing(n-1)

    left, right = 0, n-1
    # find left = right index such that
    # missing(left-1) < k <= missing(left)
    while left != right:
        pivot = (left+right)//2

        if missing(pivot) < k:
            left = pivot + 1
        else:
            right = pivot

    # kth missing number is greater than nums[left-1] and less than nums[left]
    return nums[left-1] + k - missing(left-1)

참고