Using binary search but worst case O(n)


  • 9
    S
    public class Solution {
    
    class Range {
        int start;
        int end;
        
        Range(int s, int e) {
            start = s;
            end = e;
        }
    }
    
    public List<String> summaryRanges(int[] nums) {
        
        List<String> resStr = new ArrayList<>();
        
        if (nums.length == 0) {
            return resStr;
        }
        
        List<Range> res = new ArrayList<>();
        helper(nums, 0, nums.length - 1, res);
        
        for (Range r : res) {
            if (r.start == r.end) {
                resStr.add(Integer.toString(r.start));
            } else {
                resStr.add(r.start + "->" + r.end);
            }
        }
        
        return resStr;
    }
    
    private void helper(int[] nums, int i, int j, List<Range> res) {
        if (i == j || nums[j] - nums[i] == j - i) {
            add2res(nums[i], nums[j], res);
            return;
        }
        
        int m = (i + j) / 2;
        
        helper(nums, i, m, res);
        helper(nums, m + 1, j, res);
    }
    
    private void add2res(int a, int b, List<Range> res) {
        if (res.isEmpty() || res.get(res.size() - 1).end != a - 1) {
            res.add(new Range(a, b));
        } else {
            res.get(res.size() - 1).end = b;
        }
    }
    

    }


  • 0
    Q

    Nice and clean. Didn't cross my mind to use binary search.


  • 0
    B

    I used the Binary Search too. But when I saw every discuss I felt like I overcomplicated it...

        public class Solution {
            public List<String> summaryRanges(int[] nums) {
                List<String> ans=new ArrayList<>();
                if(nums.length==0) return ans;
                int low=0;
                int high=nums.length-1;
                int index=0;
                while(index<nums.length){
                    while(high>low){
                        int mid=1+(high+low)/2;
                        if(mid-index==nums[mid]-nums[index]){
                            low=mid;
                        }else{
                            high=mid-1;
                        }
                    }
                    if(index==low) ans.add(""+nums[low]);
                    else ans.add(nums[index]+"->"+nums[low]);
                    index=++low;
                    high=nums.length-1;
                }
                return ans;
            }
        }

  • 0
    S

    Nice solution!


Log in to reply
 

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