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"]
Solution
思路和 # 228 Summary Ranges類似，但區(qū)別在于這題有重復，需要注意去重枉长。和開頭长捧、結(jié)尾數(shù)字的處理
Time: O (n)
Space: O(1)
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> result = new ArrayList<> ();
if (nums == null || nums.length == 0) {
String temp = "";
if (lower != upper) {
temp = lower + "->" + upper;
} else {
temp = String.valueOf (lower);
}
result.add (temp);
return result;
}
if (lower == upper) {
return result;
}
if (nums[0] > lower) {
String entry = (nums[0] - 1 == lower) ? String.valueOf (lower) : lower + "->" + (nums[0] - 1);
result.add (entry);
}
for (int i = 1; i < nums.length; i++) {
// 注意去重８孤隆Ｚ怂！Ｐパ薄客扎！
if (nums[i - 1] == nums[i] || nums[i - 1] + 1 == nums[i])
continue;
String entry = nums[i - 1] + 1 == nums[i] - 1 ? String.valueOf (nums[i - 1] + 1) : (nums[i - 1] + 1) + "->" + (nums[i] - 1);
result.add (entry);
}
// 注意最后一個的處理
int lastNumber = nums[nums.length - 1];
if (lastNumber < upper) {
String entry = "";
if (lastNumber + 1 == upper) {
entry = String.valueOf (upper);
} else {
entry = (lastNumber + 1) + "->" + upper;
}
result.add (entry);
}
return result;
}
}
