首页 > itarticle > 【leetcode】228. summary ranges

【leetcode】228. summary ranges

admin 11月 13, 2020 0

Description

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.

Solution

public List<String> (int[] nums) {
        int len = nums.length;
        List<String> list = new ArrayList<>();
        int count = 1;
        if (len == 0) {
            return list;
        }
        if (len == 1) {
            list.add(String.valueOf(nums[0]));
            return list;
        }
        for (int i = 0; i < len - 1; i++) {
            if (nums[i] + 1 == nums[i + 1]) {
                count++;
            } else if (nums[i] + 1 != nums[i + 1] && count == 1) {
                list.add(String.valueOf(nums[i]));
                count = 1;
            } else if (nums[i] + 1 != nums[i + 1] && count != 1) {
                list.add(String.valueOf(nums[i] - count + 1) + "->" + String.valueOf(nums[i]));
                count = 1;
             }
        }
        if (nums[len - 1] - nums[len - 2] == 1) {
            list.add(String.valueOf(nums[len - 1] - count + 1) + "->" + String.valueOf(nums[len - 1]));
        } else {
            list.add(String.valueOf(nums[len - 1]));
        }
        return list;
    }

Analyse

这里思路很简单，每一次count更新都是为了下一次的操作。在结束的时候，再统计一下结尾的值。复杂度O(n)，我觉得已经是很好的的解法了。

Optimization

public List<String> (int[] nums) {
        int len = nums.length;
        List<String> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            int a = nums[i];
            while (i + 1 < len && nums[i] + 1 == nums[i + 1]) {
                i++;
            }
            if (a != nums[i]) {
                list.add(String.valueOf(a) + "->" + String.valueOf(nums[i]));
            } else {
                list.add(String.valueOf(a));
            }
        }
        return list;
    }

Analyse

这个只是代码更短，但是明显复杂度更高，需要O(n ^ 2)复杂度，所以不推荐，还是我的方法好。