缺失的区间

Submission

运行时间: 20 ms

内存: 0.0 MB

# Analysis: calculate the difference between elements of nums 

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
        res = []
        
        if not nums:
            if lower == upper:
                res.append(str(lower))
                return res
            else:
                res.append(str(lower) + "->" + str(upper))
                return res
        
        if nums[0] != lower:
            nums.insert(0,lower - 1)
        if nums[-1] != upper:
            nums.append(upper+ 1)
            #nums.insert(len(nums) - 1, upper + 1)
        
        for i in range(len(nums) - 1):
            #print(nums[i])
            if nums[i + 1] - nums[i] > 2:
                res.append(str(nums[i] + 1) + "->" + str(nums[i + 1] - 1))
                
            elif nums[i + 1] - nums[i] == 2:
                res.append(str(nums[i] + 1))
                
            
        return res

Explain

这个题解的思路是先在原数组 nums 的首尾添加 lower-1 和 upper+1，这样可以方便处理缺失区间出现在数组两端的情况。然后遍历修改后的数组，如果相邻两个元素之差大于 2，说明它们之间存在缺失区间，将其记录到结果中。如果相邻元素之差等于 2，说明它们之间缺失了一个数，也将其记录到结果中。最后返回记录的所有缺失区间。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
        res = []
        
        # 处理数组为空的特殊情况
        if not nums:
            if lower == upper:
                res.append(str(lower))
                return res
            else:
                res.append(str(lower) + "->" + str(upper))
                return res
        
        # 在数组首尾添加 lower-1 和 upper+1，方便处理边界情况
        if nums[0] != lower:
            nums.insert(0,lower - 1)
        if nums[-1] != upper:
            nums.append(upper+ 1)
        
        # 遍历数组，找出缺失的区间
        for i in range(len(nums) - 1):
            if nums[i + 1] - nums[i] > 2:
                res.append(str(nums[i] + 1) + "->" + str(nums[i + 1] - 1))
            elif nums[i + 1] - nums[i] == 2:
                res.append(str(nums[i] + 1))
                
        return res

Explore

在原数组首尾添加lower-1和upper+1，而不是直接使用lower和upper的主要原因是简化边界处理。通过添加这两个元素，可以保证数组两端的缺失区间能够被统一和简单地处理，无需单独考虑数组开头和结尾的情况。例如，如果数组中的第一个元素大于lower，通过添加lower-1，可以直接使用相同的逻辑来判断和添加从lower到第一个元素之前的缺失区间，而无需额外的条件判断。这种方法有效地减少了代码的复杂度并提高了可读性。

当数组为空时，整个区间[lower, upper]都是缺失的。单独考虑lower等于upper的情况是因为，当lower和upper相等时，缺失的区间不是一个范围而是一个具体的数字。因此，如果lower等于upper，结果应该直接返回这个单一的数字而非一个区间。返回的格式会是这个数字本身的字符串形式。如果lower不等于upper，则返回表示整个区间的字符串，如'lower->upper'。这种处理确保了返回的结果既准确又易于理解。

在遍历数组并记录缺失区间时，决定记录单独数字还是区间的依据在于相邻两个元素的差值。如果两个相邻元素的差值等于2，这意味着它们之间正好缺失一个数字，因此应记录这个单独的数字。例如，如果两个相邻元素是3和5，那么4是缺失的，应该被记录下来。如果差值大于2，比如3和6之间，那么缺失的是一个区间[4, 5]，应记录为'4->5'。这种方法确保了所有类型的缺失都被正确记录。

确实，向数组首部或尾部插入元素可能会影响性能，尤其是在数组较大时。首部插入元素特别可能导致数组内其他元素的移动，增加时间复杂度。为了减轻这种影响，可以考虑使用额外的变量来存储首尾的元素，而不是真的在数组中插入。另外，如果实际应用中性能成为关键问题，可以考虑使用链表等数据结构，这些结构允许在首尾快速插入元素而不影响性能。在算法设计时，需要根据具体情况权衡易用性和性能，选择最合适的实现方式。