算法 |
---|
算法题 |
---|
给定一个无重复元素的有序整数数组 nums
。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说,nums
的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums
的数字 x 。
列表中的每个区间范围 [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"
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
示例 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"
示例 3:
输入:nums = []
输出:[]
示例 4:
输入:nums = [-1]
输出:["-1"]
示例 5:
输入:nums = [0]
输出:["0"]
提示:
代码:
public class Solution {
public IList<string> SummaryRanges(int[] nums) {
List<string> res = new List<string>();
int i=0,j=0;
while(j<nums.Length){
//j==nums.Length-1 这个判断比较重要,可以考虑到数组到最后的情况
if(j==nums.Length-1 || nums[j+1]-nums[j]!=1){
if(i==j) res.Add($"{nums[i]}");
else res.Add($"{nums[i]}->{nums[j]}");
i = j+1;
}
++j;
}
return res;
}
}
执行结果
通过
执行用时:232 ms,在所有 C# 提交中击败了69.77%的用户
内存消耗:30 MB,在所有 C# 提交中击败了74.42%的用户
思路解析
我们从数组的位置 00 出发,向右遍历。每次遇到相邻元素之间的差值大于 11 时,我们就找到了一个区间。遍历完数组之后,就能得到一系列的区间的列表。
在遍历过程中,维护下标low 和 high 分别记录区间的起点和终点,对于任何区间都有 low≤high。当得到一个区间时,根据low 和 high 的值生成区间的字符串表示。
代码:
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> ret = new ArrayList<String>();
int i = 0;
int n = nums.length;
while (i < n) {
int low = i;
i++;
while (i < n && nums[i] == nums[i - 1] + 1) {
i++;
}
int high = i - 1;
StringBuffer temp = new StringBuffer(Integer.toString(nums[low]));
if (low < high) {
temp.append("->");
temp.append(Integer.toString(nums[high]));
}
ret.add(temp.toString());
}
return ret;
}
}
执行结果
通过
执行用时:0 ms,在所有 Java 提交中击败了100.00%的用户
内存消耗:36.5 MB,在所有 Java 提交中击败了65.23%的用户
复杂度分析
时间复杂度:O( n )
空间复杂度:O( 1 )
C#
和 Java
两种编程语言进行解题