題目描述:
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.
就是給定一個已排序的數(shù)組,返回一個字符串數(shù)組,每個字符串表示為元素區(qū)間的合并,
LeetCode Summary Ranges
。本題是典型的two pointer 問題。
思路:
一次遍歷,使用two pointer方法,from 表示區(qū)間的起始元素,to表示區(qū)間的結(jié)束元素。
如果相鄰元素nums[i]和nums[i-1]差值為1,區(qū)間范圍+1:to = nums[i] ,注意最后元素的處理。
否則:
如果from不等于to:
將range = [from,to]添加到解集中,并更新from的位置。
如果from和to相等:
將range=from(或to)添加到解集
注意末尾元素的判斷(如果已打末尾,添加末尾元素)
實現(xiàn)代碼:
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; }}</string></string></string></string>