LeetCode -- Summary Ranges
题目描述:
Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
就是给定一个已排序的数组,返回一个字符串数组,每个字符串表示为元素区间的合并。
本题是典型的two pointer 问题。
思路:
一次遍历,使用two pointer方法,from 表示区间的起始元素,to表示区间的结束元素。
如果相邻元素nums[i]和nums[i-1]差值为1,区间范围+1:to = nums[i] ,注意最后元素的处理。
否则:
如果from不等于to:
将range = [from,to]添加到解集中,并更新from的位置。
如果from和to相等:
将range=from(或to)添加到解集
注意末尾元素的判断(如果已打末尾,添加末尾元素)
实现代码:
Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
就是给定一个已排序的数组,返回一个字符串数组,每个字符串表示为元素区间的合并。
本题是典型的two pointer 问题。
思路:
一次遍历,使用two pointer方法,from 表示区间的起始元素,to表示区间的结束元素。
如果相邻元素nums[i]和nums[i-1]差值为1,区间范围+1:to = nums[i] ,注意最后元素的处理。
否则:
如果from不等于to:
将range = [from,to]添加到解集中,并更新from的位置。
如果from和to相等:
将range=from(或to)添加到解集
注意末尾元素的判断(如果已打末尾,添加末尾元素)
实现代码:
public class Solution {
public IList<string> SummaryRanges(int[] nums) {
if(nums.Length == 0){
return new List<string>();
}
if(nums.Length == 1){
return new List<string>(){nums[0].ToString()};
}
var from = nums[0];
var to = nums[0];
var ret = new List<string>();
for(var i = 1 ;i < nums.Length; i++){
if(nums[i] - nums[i-1] == 1){
to = nums[i];
if(i == nums.Length - 1){
ret.Add(string.Format("{0}->{1}", from , to));
}
}
else{
if(from != to){
ret.Add(string.Format("{0}->{1}", from , to));
if(i == nums.Length - 1 && to != nums[nums.Length - 1]){
ret.Add(nums[i].ToString());
}
}
else{
ret.Add(from.ToString());
if(i == nums.Length - 1){
ret.Add(nums[i].ToString());
}
}
from = nums[i];
to = nums[i];
}
}
return ret;
}
}