LeetCode 163 Missing Ranges

LeetCode

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" if a != b "a" if a == 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 = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

Constraints:

-10<sup>9</sup> <= lower <= upper <= 10<sup>9</sup> 0 <= nums.length <= 100
lower <= nums[i] <= upper All the values of nums are unique.

题目大意：

给定一个范围[lower, upper]和数组表示这个范围有的数，求缺失数范围

解题思路：

简单题。也是数学题
公式为:

[nums[i-1] + 1, nums[i] - 1]

解题步骤：

N/A

注意事项：

1. 缺失数范围公式为[nums[i-1] + 1, nums[i] - 1], 需要一个函数来处理若范围内仅含一个数或多个数的情况
2. 题目条件lower, upper在数组范围之外，所以不妨将lower, upper加到数组中，同一处理，但是由于lower和upper表示缺失数，而数组表示含有数。所以将lower - 1和upper + 1加到数组
3. 数组可能为空，要特别处理Line 3

Python代码：

def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
	if not nums: # remember
		return [self.get_missing_str(lower, upper)]
	res = []
	nums.insert(0, lower - 1)
	nums.append(upper + 1)
	for i in range(1, len(nums)):
		# [nums[i-1] + 1, n - 1]
		if nums[i - 1] + 1 <= nums[i] - 1:
			res.append(self.get_missing_str(nums[i - 1] + 1, nums[i] - 1))
	return res
	
def get_missing_str(self, start, end):
	if start == end:
		return str(start)
	else:
		return str(start) + '->' + str(end)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)