Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1060.html
1060. Missing Element in Sorted Array
Level
Medium
Description
Given a sorted array A
of unique numbers, find the K-th
missing number starting from the leftmost number of the array.
Example 1:
Input: A = [4,7,9,10], K = 1
Output: 5
Explanation:
The first missing number is 5.
Example 2:
Input: A = [4,7,9,10], K = 3
Output: 8
Explanation:
The missing numbers are [5,6,8,…], hence the third missing number is 8.
Example 3:
Input: A = [1,2,4], K = 3
Output: 6
Explanation:
The missing numbers are [3,5,6,7,…], hence the third missing number is 6.
Note:
1 <= A.length <= 50000
1 <= A[i] <= 1e7
1 <= K <= 1e8
Solution
If the array nums
is empty, simply return k
since all numbers are missing in nums
.
If k
is greater than or equal to the last number in nums
, then only the numbers in nums
are not missing and all the other numbers are missing, so the k-th missing number is k + nums[0] + nums.length - 1
.
Otherwise, starting from the first letter in nums
, check each number that is greater, and if a number is not in the array, then it is missing and decrease k
by 1. The process ends until the end of nums
is reached or k
becomes 0. Finally, return the current number plus k
.
-
class Solution { public int missingElement(int[] nums, int k) { if (nums == null || nums.length == 0) return k; int length = nums.length; if (k >= nums[length - 1]) return k + nums[0] + length - 1; int num = nums[0]; int index = 1; while (index < length && k > 0) { num++; if (num == nums[index]) index++; else k--; } return num + k; } }
-
class Solution { public: int missingElement(vector<int>& nums, int k) { auto missing = [&](int i) { return nums[i] - nums[0] - i; }; int n = nums.size(); if (k > missing(n - 1)) { return nums[n - 1] + k - missing(n - 1); } int l = 0, r = n - 1; while (l < r) { int mid = (l + r) >> 1; if (missing(mid) >= k) { r = mid; } else { l = mid + 1; } } return nums[l - 1] + k - missing(l - 1); } };
-
class Solution: def missingElement(self, nums: List[int], k: int) -> int: def missing(i: int) -> int: return nums[i] - nums[0] - i n = len(nums) if k > missing(n - 1): return nums[n - 1] + k - missing(n - 1) l, r = 0, n - 1 while l < r: mid = (l + r) >> 1 if missing(mid) >= k: r = mid else: l = mid + 1 return nums[l - 1] + k - missing(l - 1)
-
func missingElement(nums []int, k int) int { missing := func(i int) int { return nums[i] - nums[0] - i } n := len(nums) if k > missing(n-1) { return nums[n-1] + k - missing(n-1) } l, r := 0, n-1 for l < r { mid := (l + r) >> 1 if missing(mid) >= k { r = mid } else { l = mid + 1 } } return nums[l-1] + k - missing(l-1) }