[Leetcode] Summary Ranges 統(tǒng)計(jì)區(qū)間

Youngdze 發(fā)布于2019-08-14 12:33 / 1652人閱讀

摘要：雙層迭代法復(fù)雜度時間空間思路外層的循環(huán)控制每個的起點(diǎn)，內(nèi)層的循環(huán)控制之內(nèi)的遞增。每當(dāng)遍歷完一個，就把它記錄到結(jié)果中，并更新下一個的起點(diǎn)。這里的技巧是，判斷一個數(shù)是否是在內(nèi)的，只要就行了，即值之差等于下標(biāo)之差。

Summary Ranges

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"].

雙層迭代法 復(fù)雜度

時間 O(N) 空間 O(N)

思路

外層的while循環(huán)控制每個range的起點(diǎn)，內(nèi)層的while循環(huán)控制range之內(nèi)的遞增。每當(dāng)遍歷完一個range，就把它記錄到結(jié)果中，并更新下一個range的起點(diǎn)。這里的技巧是，判斷一個數(shù)是否是在range內(nèi)的，只要nums[start + range] - nums[start] = range就行了，即值之差等于下標(biāo)之差。

代碼

public class Solution {
    public List summaryRanges(int[] nums) {
        List res = new LinkedList();
        if(nums.length == 0) return res;
        StringBuilder tmp = new StringBuilder();
        int start = 0;
        while(start < nums.length){
            int range = 1;
            // 遍歷當(dāng)前range內(nèi)的所有數(shù)
            while(start + range < nums.length && (nums[start + range] - nums[start]) == range){
                range++;
            }
            // 遍歷完了當(dāng)前range，將其加入結(jié)果中
            tmp.append(nums[start]);
            if(range > 1){
                tmp.append("->");
                tmp.append(nums[start+range-1]);
            }
            res.add(tmp.toString());
            tmp = new StringBuilder();
            // 更新下一個range的起點(diǎn)
            start = start + range;
        }
        return res;
    }
}