Missing Ranges

medium, Array/String

Question:

给定范围[0,99]的有序整数序列，范围丢失的范围

For example
给定 [0, 1, 3, 50, 75]
返回[“2”, “4->49”, “51->74”, “76->99”]

Qestions by reviewers:

1. 序列为空如何处理？
   返回["0->99"]
2. 序列全覆盖如何处理？
   返回[]

Solution

问题简单的比较相邻两数即可，由于序列的第一个和最后一个数处于边界，我们可以调价psudo intergers方便处理：-1 和100。问题可以扩展到任意范围。

class Solution(object):
    def findMissingRanges(self, vals, start, end):
        """
        :type vals: [int]
        :type start: int
        :type end: int
        :rtype: [str]
        """

    res = []
    pre = start - 1
    for i in xrange(len(vals)+1):
        cur = end+1 if i == len(vals) else vals[i]
        if cur - pre >= 2:
            res.append(getRange(pre+1, cur-1))
        prv = cur
    return res

    def getRange(from, to):
        """
        :type from: int
        :type to: int
        :rtype: string
        """
        if from == to: 
            return str(from)
        else:
            return str(from) + '->' + str(to)