Solution with O(log(n))


  • 0
    T

    public class Solution {

    public IList<string> SummaryRanges(int[] nums) {
        IList<string> result = new List<string>();
        
        if(nums.Length == 0)
            return result;
        
        IList<int[]> t_result = new List<int[]>();
        
        dfs(nums,0,nums.Length-1,t_result);
        
        foreach(var item in t_result){
            if(item[0] == item[1]){
                result.Add(item[1]+"");
            }else{
                result.Add(item[0]+"->"+item[1]);
            }
        }
        
        
        return result;
    }
    
    private void dfs(int[] nums,int low,int high,IList<int[]> result){
        if(low > high){
            return;
        }
        
        if(high-low == nums[high]-nums[low]){
            result.Add(new int[]{nums[low],nums[high]});
            return;
        }
        
        int mid = low + (high-low)/2;
        
        dfs(nums,low,mid,result);
        int midIndex = result.Count;
        dfs(nums,mid+1,high,result);
        
        if(result[midIndex-1][1] == result[midIndex][0]-1){
            result[midIndex-1][1] = result[midIndex][1];
            result.RemoveAt(midIndex);
        }
    }
    

    }


  • 0

    It's not O(log n); extreme counterexample is like [1, 3, 5, 7, 9, 13, ...].


Log in to reply
 

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