228. Summary Ranges

  • 28.7%

https://leetcode.com/problems/summary-ranges/description/

Given a sorted integer array without duplicates, return the summary of its ranges.

1
2
3
4
5
6
Example 1:
Input: [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Example 2:
Input: [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]

方法一:

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> res;
int i=0, n=nums.size();
while(i<n){
int j = i;
while(j+1<n && nums[j+1]==nums[j]+1)
j++;
if(j==i)
res.push_back(to_string(nums[i]));
else{
string s = to_string(nums[i]) + "->" + to_string(nums[j]);
res.push_back(s);
}
i = j+1;
}
return res;
}
};

0ms, 14.20%, June.18th, 2016

https://leetcode.com/discuss/42229/10-line-c-easy-understand

10 line c++ easy understand

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<string> summaryRanges(vector<int>& nums) {
const int size_n = nums.size();
vector<string> res;
if ( 0 == size_n) return res;
for (int i = 0; i < size_n;) {
int start = i, end = i;
while (end + 1 < size_n && nums[end+1] == nums[end] + 1) end++;
if (end > start) res.push_back(to_string(nums[start]) + "->" + to_string(nums[end]));
else res.push_back(to_string(nums[start]));
i = end+1;
}
return res;
}

https://discuss.leetcode.com/topic/17154/9-lines-c-0ms-solution

9 lines, c++, 0ms solution

1
2
3
4
5
6
7
8
9
10
11
vector<string> summaryRanges(vector<int>& nums) {
int i = 0, size = nums.size();
vector<string> result;
while(i < size){
int j = 1;
while(i + j < size && nums[i + j] - nums[i] == j) ++j;
result.push_back(j <= 1 ? to_string(nums[i]) : to_string(nums[i]) + "->" + to_string(nums[i + j - 1]));
i += j;
}
return result;
}

https://discuss.leetcode.com/topic/17177/idea-1-liner-group-by-number-index

Idea + 1-Liner: Group by number-index

The Idea

The difference between a number and its index identifies the range. Consider the given example input:

1
2
3
numbers:  [0, 1, 2, 4, 5, 7]
indexes: [0, 1, 2, 3, 4, 5]
subtract: [0, 0, 0, 1, 1, 2]

You can see I have three differences (0, 1 and 2), corresponding to the three ranges. That can then be used to group the elements.

Solution 1

Ruby and Python can exploit it particularly well, thanks to their groupby functions:

Python:

1
2
3
def summaryRanges(self, nums):
return [re.sub('->.*>', '->', '->'.join(`n` for i, n in g))
for _, g in itertools.groupby(enumerate(nums), lambda (i, n): n-i)]

Solution 2

Here I build two dicts, telling me the first and last number of each range. For the given example I get:

1
2
first = {0: 0, 1: 4, 2: 7}
last = {0: 2, 1: 5, 2: 7}

The code:

1
2
3
4
def summaryRanges(self, nums):
diff = [(n-i, n) for i, n in enumerate(nums)]
first, last = dict(diff[::-1]), dict(diff)
return [`n` + ('->'+`last[d]`)*(n<last[d]) for d, n in sorted(first.items())]

Solution 3

Storing [first, last] for each range in a dict (last being optional).

1
2
3
4
5
def summaryRanges(self, nums):
ranges = collections.defaultdict(list)
for i, n in enumerate(nums):
ranges[n-i][1:] = n,
return ['->'.join(map(str, r)) for r in sorted(ranges.values())]

https://discuss.leetcode.com/topic/17094/6-lines-in-python

6 lines in Python

Three versions of the same algorithm, all take O(n) time.

Solution 1

Just collect the ranges, then format and return them.

1
2
3
4
5
6
7
def summaryRanges(self, nums):
ranges = []
for n in nums:
if not ranges or n > ranges[-1][-1] + 1:
ranges += [],
ranges[-1][1:] = n,
return ['->'.join(map(str, r)) for r in ranges]

Solution 2

A variation of solution 1, holding the current range in an extra variable r to make things easier. Note that r contains at most two elements, so the in-check takes constant time.

1
2
3
4
5
6
7
8
def summaryRanges(self, nums):
ranges, r = [], []
for n in nums:
if n-1 not in r:
r = []
ranges += r,
r[1:] = n,
return ['->'.join(map(str, r)) for r in ranges]

Solution 3

A tricky short version.

1
2
3
4
5
6
7
8
def summaryRanges(self, nums):
ranges = r = []
for n in nums:
if `n-1` not in r:
r = []
ranges += r,
r[1:] = `n`,
return map('->'.join, ranges)

About the commas :-)

Three people asked about them in the comments, so I’ll also explain it here as well. I have these two basic cases:

1
2
ranges += [],
r[1:] = n,

Why the trailing commas? Because it turns the right hand side into a tuple and I get the same effects as these more common alternatives:

1
2
3
4
5
ranges += [[]]
or
ranges.append([])

r[1:] = [n]

Without the comma, …

  • ranges += [] wouldn’t add [] itself but only its elements, i.e., nothing.
  • r[1:] = n wouldn’t work, because my n is not an iterable.

Why do it this way instead of the more common alternatives I showed above? Because it’s shorter and faster (according to tests I did a while back).


https://discuss.leetcode.com/topic/17934/my-easy-to-understand-python-solution

My easy to understand Python solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def summaryRanges(self, nums):
if not nums:
return []
res, i, start = [], 0, 0
while i < len(nums)-1:
if nums[i]+1 != nums[i+1]:
res.append(self.printRange(nums[start], nums[i]))
start = i+1
i += 1
res.append(self.printRange(nums[start], nums[i]))
return res

def printRange(self, l, r):
if l == r:
return str(l)
else:
return str(l) + "->" + str(r)

Solution Mine:

40ms, 84.94%, June.18th, 2016

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
class Solution(object):
def summaryRanges(self, nums):
"""
:type nums: List[int]
:rtype: List[str]
"""
if not nums:
return []
if len(nums)==1:
return [str(nums[0])]
rtype = []
p1 = 0
p2 = 0
n = len(nums)
while p1 < n-1:
while p2 < n-1 and nums[p2] + 1 == nums[p2+1]:
p2 += 1
if p1 == p2:
rtype.append(str(nums[p1]))
else:
tmp = str(nums[p1]) + '->' + str(nums[p2])
rtype.append(tmp)
p2 += 1
p1 = p2
if p1 == n-1:
rtype.append(str(nums[-1]))
return rtype

Solution 1:

48ms, 38.46%, June.18th, 2016

https://leetcode.com/discuss/42199/6-lines-in-python

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def summaryRanges(self, nums):
"""
:type nums: List[int]
:rtype: List[str]
"""
ranges = []
for n in nums:
if not ranges or n > ranges[-1][-1] + 1:
ranges += [],
ranges[-1][1:] = n,
return ['->'.join(map(str, i)) for i in ranges]

1ms, 5.00%, June.18th, 2016

https://leetcode.com/discuss/42290/accepted-java-solution-easy-to-understand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> list = new ArrayList();
if(nums.length == 1){
list.add(nums[0] + "");
return list;
}

for(int i=0; i < nums.length; i++){
int a = nums[i];
while(i+1<nums.length && nums[i+1] - nums[i] ==1) i++;
if(a != nums[i]) list.add(a + "->" + nums[i]);
else list.add(a+"");
}
return list;
}
}
谢谢你,可爱的朋友。