LC: 1060. Missing Element in Sorted Array
https://leetcode.com/problems/missing-element-in-sorted-array/
1060. Missing Element in Sorted Array
Given an integer array nums which is sorted in ascending order and all of its elements are unique and given also an integer k, return the kth missing number starting from the leftmost number of the array.
Example 1:
Input: nums = [4,7,9,10], k = 1
Output: 5
Explanation: The first missing number is 5.Example 2:
Input: nums = [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: nums = [1,2,4], k = 3
Output: 6
Explanation: The missing numbers are [3,5,6,7,...], hence the third missing number is 6.Constraints:
1 <= nums.length <= 5 * 1041 <= nums[i] <= 107numsis sorted in ascending order, and all the elements are unique.1 <= k <= 108
Follow up: Can you find a logarithmic time complexity (i.e., O(log(n))) solution?
Missing Element in Sorted Array
The Essence:
Die Anzahl der Elemente, die vor einer Zahl fehlen, ist von dem Index und Wert der Zahl abhängig: fehlende(i) = nums[i] - nums[0] - i
Man kann bemerken, dass für j>i fehlende(j) ≥ fehlende(i) gilt.
Details:
Mit der beschriebenen Intuition erkennt man, dass das Array nach fehlende(i) sortiert ist. Man kann also binäre Suche benutzen, um die k-te fehlende Zahl zu finden.
Solution(s) and Further Explanation:
Default Code:
Last updated