0163._Missing_Ranges.md

163. Missing Ranges

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/missing-ranges/

内容描述

Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

Example:

Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

这道题就是无脑遍历，小心一下一个恶心的case就是[1,1,1]，lower=1，upper=1，其他没有问题

beats 99.75%

class Solution(object):
    def findMissingRanges(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: List[str]
        """
        if not nums or len(nums) == 0:
            return [str(lower) + '->' + str(upper) if lower != upper else str(lower)]
        
        res = []
        if lower < nums[0]:
            missing = str(lower) + '->' + str(nums[0]-1) if lower != nums[0]-1 else str(lower)
            res.append(missing)
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                continue
            if nums[i] != nums[i+1] - 1:
                if nums[i]+1 != nums[i+1]-1:
                    missing = str(nums[i]+1) + '->' + str(nums[i+1]-1)
                else:
                    missing = str(nums[i]+1)
                res.append(missing)
        if upper > nums[-1]:
            missing = str(nums[-1]+1) + '->' + str(upper) if upper != nums[-1]+1 else str(upper)
            res.append(missing)
        return res