Leetcode Note: Go - Kth Missing Positive Number
Kth Missing Positive Number - LeetCode
https://leetcode.com/problems/kth-missing-positive-number/
- Go 言語で取り組んだメモ
回答
Golang binary search solution - Kth Missing Positive Number - LeetCode
https://leetcode.com/problems/kth-missing-positive-number/solutions/1004728/golang-binary-search-solution/
func findKthPositive(arr []int, k int) int {
max := arr[len(arr) - 1]
//if kth position number is bigger than last element of arr
if k > max - len(arr) {
return k + len(arr)
}
//if kth position number is smaller than first element of arr
if k <= arr[0] - 1 {
return k
}
l := 0
r := len(arr) - 1
//binary search
//arr[idx] - idx - 1 is the number of missing integers of position idx
for l + 1 < r {
mid := r - (r - l) / 2
if arr[mid] - mid - 1 < k {
l = mid
} else {
r = mid
}
}
return k + l + 1
}