228. Summary Ranges

发表于 | 更新于: | 分类于 | 本文总阅读量 次
| 字数统计: 1,288 | 阅读时长 ≈ 8
  • 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;
    }
}
谢谢你，可爱的朋友。