2015年10月24日星期六

Leetcode 163 Missing Ranges

Given a sorted integer array where the range of elements are [lowerupper] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75]lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].
Solution 1: iterate the array, O(n) solution below:
 public class Solution {  
   public List<String> findMissingRanges(int[] nums, int lower, int upper) {  
     int n=nums.length;  
     List<String> res=new ArrayList<>();  
     for (int i=0; i<n; i++) {  
       if (nums[i]<lower) continue;  
       else if (nums[i]==lower) lower++;  
       else {  
         int hi=Math.min(nums[i]-1,upper);  
         if (lower==hi) res.add(String.valueOf(lower));  
         else if (lower<hi) res.add(String.valueOf(lower)+"->"+String.valueOf(hi));  
         lower=nums[i]+1;  
       }  
       if (lower>upper) break;  
     }  
     if (lower==upper) res.add(String.valueOf(lower));  
     else if (lower<upper) res.add(String.valueOf(lower)+"->"+String.valueOf(upper));  
     return res;  
   }  
 }  

没有评论:

发表评论