163. Missing Ranges
Medium
Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.
Example:
Input: nums =[0, 1, 3, 50, 75]
, lower = 0 and upper = 99, Output:["2", "4->49", "51->74", "76->99"]
* keep update lower bound "l"
* use "long long" to resolve overflow
========
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | typedef long long ll; class Solution { public: void updateIntv(ll l, ll r, vector<string>& ret) { if(l==r) ret.push_back(to_string(l)); if(l<r) ret.push_back(to_string(l)+"->"+to_string(r)); } vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) { vector<string> ret; int n = nums.size(), i = 0; ll l = lower; while(i<n){ ll v = nums[i++]; updateIntv(l, v-1, ret); l = v+1; } updateIntv(l, upper, ret); return ret; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public List<String> findMissingRanges(int[] nums, int lower, int upper) { List<String> list = new ArrayList<>(); int left = lower; for(int i : nums){ int right = i-1; if(right>left){ list.add(left + "->" + right); }else if(right==left){ list.add(String.valueOf(left)); } left = i+1; } if(left<=upper){ if(left==upper) list.add(String.valueOf(left)); else list.add(left + "->" + upper); } return list; } } |
No comments:
Post a Comment