228. Summary Ranges

reboot329 2019-06-20 原文

刷
June-19-2019

这个题居然也没记过，可能当时觉得太简单了。

楞做法

    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if (nums.length == 0) return result;
        
        StringBuilder sb = new StringBuilder();
        int prev = nums[0];
        sb.append(prev);
        for (int i = 1; i < nums.length; i ++) {
            int temp = nums[i];
            if (temp == prev + 1) {
                prev = temp;
            } else {
                if (prev != Integer.valueOf(sb.toString())) {
                    sb.append("->").append(prev);
                }
                result.add(sb.toString());
                sb = new StringBuilder();
                sb.append(temp);
                prev = temp;
            }
        }
        
        if (prev != Integer.valueOf(sb.toString())) {
                sb.append("->").append(prev);
        }
        result.add(sb.toString());
        return result; 
    }

然后另一种是通过nums[r] – nums[l] == r – l 来迅速完成l->r
缺点是在[1,3,5,7,9,11]这种每次R都要从最右边到最左边，反而变成O(n²)了

    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if (nums.length == 0) return result;
        
        int r = nums.length - 1;
        for (int l = 0; l < nums.length; l ++) {
            while (l <= r) {
                if (nums[l] == nums[r]) {
                    result.add(new StringBuilder(Integer.toString(nums[l])).toString());
                    r = nums.length - 1;
                    break;
                } else if (nums[r] - nums[l] == r - l) {
                    result.add(new StringBuilder(Integer.toString(nums[l]))
                                                            .append("->")
                                                            .append(nums[r])
                                                            .toString());
                    l = r;
                    r = nums.length - 1;
                    break;
                } else {
                    r --;
                }
            }
        }

        return result;
    }

其实可以二分，类似于归并排序的办法，缺点是merge 时候麻烦点，得处理[1-3][4-5]和[3][4]这种情况= =然后我有点懒就没写。