leetcode163.缺失的区间，模拟
leetcode163.缺失的区间
给定一个排序的整数数组 nums ，其中元素的范围在 闭区间 [lower, upper] 当中，返回不包含在数组中的缺失区间。
示例：
输入: nums = [0, 1, 3, 50, 75], lower = 0 和 upper = 99,
输出: [“2”, “4->49”, “51->74”, “76->99”]
题目分析
本题要求找出给定整数数组 nums 中缺失的区间。数组 nums 已经排序，且数组中的元素均为闭区间。需要找到所有不在 nums 中的闭区间，并返回这些区间的字符串表示形式。
算法步骤
- 初始化：在
nums数组前后分别添加lower-1和upper+1，以便处理边界情况。 - 遍历数组：遍历处理后的数组，比较相邻元素。
- 判断区间：
- 如果相邻元素差为1，表示没有缺失的区间，继续遍历。
- 如果相邻元素差为2，表示缺失一个元素，将这个元素添加到结果中。
- 如果相邻元素差大于2，表示缺失一个区间，将这个区间添加到结果中。
- 返回结果：返回所有缺失区间的字符串表示形式。
算法流程
算法代码
class Solution {
public:vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {nums.insert(nums.begin(),lower-1);nums.push_back(upper+1);vector<string> ans;for(int i = 1;i<nums.size();i++)if(nums[i]-nums[i-1]==1) continue;else if(nums[i]-nums[i-1]==2) ans.push_back(to_string(nums[i]-1));else ans.push_back(to_string(nums[i-1]+1)+"->"+to_string(nums[i]-1));return ans;}
};算法分析
- 时间复杂度：O(n)，其中 n 是数组
nums的长度。我们只需要遍历一次数组。 - 空间复杂度：O(1)，除了返回结果所用的空间外，我们只需要常数级别的额外空间。
- 易错点：处理边界情况时，需要在数组前后添加
lower-1和upper+1，以正确处理包含边界值的情况。 - 注意点：在转换区间为字符串时，注意单个元素和区间的不同表示方式。
相似题目
| 题目 | 链接 |
|---|---|
| LeetCode 228. Summary Ranges | 求连续区间的总结 |
| LeetCode 163. Missing Ranges | 本题的变体，更接近原题 |
| LeetCode 229. Majority Element II | 找出数组中出现次数超过 ⌊ n/3 ⌋ 次的元素 |