- 28.7%

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

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

1 | Example 1: |

方法一：

我的代码实现：

1 | class Solution { |

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

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

10 line c++ easy understand

1 | vector<string> summaryRanges(vector<int>& nums) { |

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

9 lines, c++, 0ms solution

1 | vector<string> summaryRanges(vector<int>& nums) { |

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 | numbers: [0, 1, 2, 4, 5, 7] |

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 | def summaryRanges(self, nums): |

Solution 2

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

1 | first = {0: 0, 1: 4, 2: 7} |

The code:

1 | def summaryRanges(self, nums): |

Solution 3

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

1 | def summaryRanges(self, nums): |

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 | def summaryRanges(self, nums): |

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 | def summaryRanges(self, nums): |

Solution 3

A tricky short version.

1 | def summaryRanges(self, nums): |

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 | ranges += [], |

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 | ranges += [[]] |

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 | def summaryRanges(self, nums): |

Solution Mine:

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

1 | class Solution(object): |

Solution 1:

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

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

1 | class Solution(object): |

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

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

1 | public class Solution { |