1539. Kth Missing Positive Number

Problem

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Return the k^th positive integer that is missing from this array.

Example 1.

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5^th missing positive integer is 9.

Example 2.

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2^nd missing positive integer is 6.

Constraints:

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• arr[i] < arr[j] for 1 <= i < j <= arr.length

개인적으로 난이도가 medium정도 되는거 같았다

Solution

impl Solution{
    pub fn find_kth_positive(arr:Vec<i32>, k:i32)->i32{
        let mut l:i32 = 0;
        let mut h:i32 = (arr.len()-1) as i32;
        while l<=h{
            let m = (l+(h-l)/2) as usize;
            let r = arr[m];
            //(m+1) 은 m번째 index에 있는 값을 나타낸다. 값이 strictly increasing order로 되어있기 때문
            //r-(m+1) = r-m-1;
            let diff = r-(m as i32) -1;
            // diff가 목표로 하는 순번(k)에 가까워지려고 노력하자
            if diff < k {
                l = (m as i32) + 1;
            } else {
                h = (m as i32) - 1;
            }
        다
        //l이 있는 위치는 숫자 k번 만큼 빠져있는 인덱스다. 그래서 k를 더해주면 빠진 k번째 값을 얻을수 있다. 
        l+k;
    }
}