LC: 163. Missing Ranges
163. Missing Ranges
You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.
A number x is considered missing if x is in the range [lower, upper] and x is not in nums.
Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.
Each range [a,b] in the list should be output as:
"a->b"ifa != b"a"ifa == b
Example 1:
Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2","4->49","51->74","76->99"]
Explanation: The ranges are:
[2,2] --> "2"
[4,49] --> "4->49"
[51,74] --> "51->74"
[76,99] --> "76->99"Example 2:
Input: nums = [], lower = 1, upper = 1
Output: ["1"]
Explanation: The only missing range is [1,1], which becomes "1".Example 3:
Example 4:
Example 5:
Constraints:
-109 <= lower <= upper <= 1090 <= nums.length <= 100lower <= nums[i] <= upperAll the values of
numsare unique.
The Essence: Diese Aussage aus der Problemstellung ist genau die Kernaussage des Problems:
Since the input array, nums, is sorted ascendingly and all the elements in it are within the given [lower, upper] bounds, we can simply check consecutive elements to see if they differ by one or not. If they don't, then we have found a missing range.
When nums[i] - nums[i-1] == 1, we know that there are no missing elements between nums[i-1] and nums[i]. When nums[i] - nums[i-1] > 1, we know that the range of elements, [nums[i-1] + 1, nums[i] - 1], is missing.
Solution(s): Die detaillierte Implementierung ist hier zu finden:
Default Code:
Last updated