IT博客汇 | 163. Missing Ranges

163. Missing Ranges

10k发表于 2024-01-21 00:00:00

Question

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are within the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the shortest sorted list of ranges that exactly covers all the missing numbers**. That is, no element of nums is included in any of the ranges, and each missing number is covered by one of the ranges.

Example 1:

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: [[2,2],[4,49],[51,74],[76,99]]
Explanation: The ranges are:
[2,2]
[4,49]
[51,74]
[76,99]

Example 2:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

Constraints:

-109 <= lower <= upper <= 109
0 <= nums.length <= 100
lower <= nums[i] <= upper
All the values of nums are unique.

Algorithm

Implementation based on the description requirements
Handle missing range first, let things be simple at first
Then handle the lower and upper

Code

class Solution {
    public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            list.add(lower);
            list.add(upper);
            res.add(new ArrayList<>(list));
            return res;
        } // don't forget to handle this;
        
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 && nums[i] != lower) {
                list.add(lower);
                list.add(nums[i] - 1);
                res.add(new ArrayList<>(list));
                list = new ArrayList<>();
            } else if (i > 0) {
                if (nums[i] != nums[i - 1] + 1) {
                    list.add(nums[i - 1] + 1);
                    list.add(nums[i] - 1);
                    res.add(new ArrayList<>(list));
                    list = new ArrayList<>();    
                }
            }
        }
        
        if (nums[nums.length - 1] != upper) {
            list.add(nums[nums.length - 1] + 1);
            list.add(upper);
            res.add(new ArrayList<>(list));
            list = new ArrayList<>();
        } // and don;t put those upper handler into loop;
        
        return res;
    }
}