victory的博客

长安一片月，万户捣衣声

0%

leetcode | 228.汇总区间

发表于 分类于 ， ， ，

228.汇总区间

题目描述

给定一个 无重复元素 的 有序 整数数组 nums 。
返回数组中的连续区间范围列表。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
“a->b” ，如果 a != b
“a” ，如果 a == b

示例 1：

1
2
3
4
5
6
输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

题目链接

思路

  1. 一次遍历
    我们从数组的位置 0 出发，向右遍历。每次遇到相邻元素之间的差值大于 1 时，我们就找到了一个区间。遍历完数组之后，就能得到一系列的区间的列表。
    在遍历过程中，维护下标 low 和 high 分别记录区间的起点和终点，对于任何区间都有 low≤high。当得到一个区间时，根据 low 和 high 的值生成区间的字符串表示。
    (1)当 low<high 时，区间的字符串表示为 “low→high”；
    (2)当 low=high 时，区间的字符串表示为 “low”。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    class Solution(object):
    	def summaryRanges(self, nums):
    		"""
            :type nums: List[int]
            :rtype: List[str]
            """
    		if not nums:
    			return []
    		result = []
    		temp_list = [nums[0]]
    		for i in range(1, len(nums)):
    			if nums[i] == nums[i - 1] + 1:
    				temp_list.append(nums[i])
    			else:
    				if temp_list[0] == temp_list[-1]:
    					result.append(str(temp_list[0]))
    				else:
    					result.append(str(temp_list[0]) + "->" + str(temp_list[-1]))
    				temp_list = list()
    				temp_list.append(nums[i])
    		if temp_list:
    			if temp_list[0] == temp_list[-1]:
    				result.append(str(temp_list[0]))
    			else:
    				result.append(str(temp_list[0]) + "->" + str(temp_list[-1]))
    		return result
    	
    	def summaryRanges1(self, nums):
    		result = []
    		i = 0
    		n = len(nums)
    		while i < n:
    			low = i
    			i += 1
    			while i < n and nums[i] == nums[i - 1] + 1:
    				i += 1
    			high = i - 1
    			temp = str(nums[low])
    			if low < high:
    				temp += "->"
    				temp += str(nums[high])
    			result.append(temp)
    		return result
    			
    if __name__ == "__main__":
    	slt = Solution()
    	nums = [0, 1, 2, 4, 5, 7]
    	# nums = [0, 2, 3, 4, 6, 8, 9]
    	# nums = []
    	# result = slt.summaryRanges(nums)
    	result = slt.summaryRanges1(nums)
    	print(result)