【无标题】

您所在的位置:网站首页 去掉无序列表前面样式的设置 【无标题】

【无标题】

2023-06-18 21:38| 来源: 网络整理| 查看: 265

题目:

给定一个  无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出:

"a->b" ,如果 a != b "a" ,如果 a == b  

示例 1:

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

输入:nums = [0,2,3,4,6,8,9] 输出:["0","2->4","6","8->9"] 解释:区间范围是: [0,0] --> "0" [2,4] --> "2->4" [6,6] --> "6" [8,9] --> "8->9"  

提示:

0 List[str]: # 如果nums为空列表,则直接返回空列表 if not nums: return [] # 定义一个空列表res,用于存储结果 res = [] # 定义一个变量start,用于记录当前连续序列的起始值 start = nums[0] # 遍历nums中的每个元素 for i in range(1, len(nums)): # 如果当前元素不等于前一个元素加1,说明当前连续序列已经结束 if nums[i] != nums[i-1]+1: # 如果当前连续序列只有一个元素,直接将该元素转为字符串并添加到res中 if nums[i-1] == start: res.append(str(start)) # 如果当前连续序列有多个元素,将该序列的起始值和结束值转为字符串并用"->"连接,然后添加到res中 else: res.append(str(start) + "->" + str(nums[i-1])) # 更新start为当前元素,开始下一个连续序列的计算 start = nums[i] # 处理最后一个连续序列 if nums[-1] == start: res.append(str(start)) else: res.append(str(start) + "->" + str(nums[-1])) # 返回结果列表res return res 2.while循环: # 定义一个函数,输入为一个整数列表nums,输出为一个字符串列表 class Solution: def summaryRanges(self, nums: List[int]) -> List[str]: # 定义一个空列表li,用于存储结果 li = [] # 定义变量i,初始化为0,表示当前遍历到的起始位置 i = 0 # 循环遍历整个nums列表 while i < len(nums): # 定义变量j,初始化为i+1,表示当前遍历到的结束位置 j = i + 1 # 循环遍历nums列表,直到找到不连续的位置 while j < len(nums) and nums[j] == nums[i] + j - i: j += 1 # 将连续的数字范围转换为字符串,并添加到li列表中 li.append(str(nums[i]) if i == j - 1 else str(nums[i]) + '->' + str(nums[j - 1])) # 更新i的值,指向下一个未处理的数字 i = j # 返回结果列表li return li 总结:

 

这道题可以使用双指针来解决。我们用两个指针 `left` 和 `right` 来表示当前区间的左右端点。初始时,它们都指向数组的第一个元素。然后我们不断地将右指针向右移动,直到区间中的所有元素都被覆盖。此时,我们就找到了以左指针为起点的最短区间。我们将这个区间加入答案数组,并将左指针移到右指针的下一个位置,继续寻找下一个区间。

具体来说,我们每次将右指针向右移动一位。如果当前区间中的所有元素都被覆盖,那么我们就将这个区间加入答案数组,并将左指针移到右指针的下一个位置。我们需要注意处理数组末尾的边界情况。

时间复杂度是 $O(n)$,其中 $n$ 是数组的长度。



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3