163缺失的区间

tech2022-12-02  104

题目描述: 给定一个排序的整数数组 nums ,其中元素的范围在 闭区间 [lower, upper] 当中,返回不包含在数组中的缺失区间。

示例: 输入: nums = [0, 1, 3, 50, 75], lower = 0 和 upper = 99, 输出: [“2”, “4->49”, “51->74”, “76->99”]

方法1: 主要思路: (1)使用一次遍历的方式,遍历的过程中,使用变量split存储每个可能的缺失区间的左边界,然后通过数组中的元素,确定右边界的可行性;

class Solution { public: vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) { vector<string> res; long split=lower;//存储每个可能的左边界 for(int i=0;i<nums.size();++i){ if(nums[i]==split){ ++split;//增大,和++i同步 } else if(nums[i]>split){//存在缺失的边界,因为是比上述最小值大1 if(nums[i]-split>1){//若是范围超过1 res.push_back(to_string(split)+"->"+to_string(nums[i]-1)); } else{//若是范围内只有一个元素 res.push_back(to_string(split)); } split=long(nums[i])+1; } } //处理尾部的情形 if(split==upper){ res.push_back(to_string(split)); } else if(split<upper){ res.push_back(to_string(split)+"->"+to_string(upper)); } return res; } };
最新回复(0)