16-line, Log(n), naiiiive c++ ( and what else to expect?! )


  • 2
    M
    class Solution {
    public:
        vector<string> summaryRanges(vector<int>& nums) {
            int start=0, len=nums.size();
            vector<string> ans;
            while (start<len) {
                int l=start, r=len-1;
                while (l<r) {
                    int m = l+(r-l)/2 + 1;
                    if ((long long)nums[m] - (long long)nums[start] > m-start)
                        r = m-1;
                    else
                        l = m;
                }
                if (l==start)
                    ans.push_back(to_string(nums[start]));
                else
                    ans.push_back(to_string(nums[start]) + "->" + to_string(nums[l]));
                start = l+1;
            }
            return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.