2026-11-16:找到所有数组中消失的数字Ⅱ。用go语言,给定一个整数序列 nums,并给出闭区间端点 lower 和 upper。把闭区间 [lower, upper] 内所有没有在 nums 中出现过的整数看作空缺值。要求找出这些空缺值组成的连续段,每一段用起点和终点表示,形成形如 [start, end] 的结果。所有连续空缺应合并为一段,结果按起点从小到大排列;如果该区间内没有空缺值,则返回空数组。
1 <= nums.length <= 100000。
1 <= nums[i] <= 100000。
1 <= lower <= upper <= 100000。
输入: nums = [3,9,7], lower = 1, upper = 12。
输出: [[1,2],[4,6],[8,8],[10,12]]。
解释:
缺失整数为 [1, 2, 4, 5, 6, 8, 10, 11, 12]。
将这些缺失整数合并成最少数量的连续区间后,得到 [1, 2]、[4, 6]、[8, 8] 和 [10, 12]。
因此,答案为 [[1, 2], [4, 6], [8, 8], [10, 12]]。
题目来自力扣4031。
大体步骤如下:
1. 加入边界哨兵
代码先把lower-1和upper+1追加到nums中。
这样做的目的是保证即使[lower, upper]的开头或结尾存在空缺,也能通过相邻元素差被发现。
例如输入nums = [3,9,7]、lower = 1、upper = 12,加入后得到[3,9,7,0,13]。2. 对数组排序
使用slices.Sort(nums)将数组升序排序。
排序后,数组中相邻元素之间的“空隙”就对应可能缺失的整数段。
上述例子排序后为[0,3,7,9,13]。3. 二分查找扫描范围左端点
l := sort.SearchInts(nums, lower+1)找的是排序数组中第一个大于等于lower+1的位置。
这个位置之前的相邻差主要涉及lower之前的数,不需要生成结果;从l开始检查,可以覆盖lower附近可能缺失的区间。
例子中lower+1 = 2,排序数组中第一个大于等于 2 的元素是 3,所以l = 1。4. 二分查找扫描范围右端点
r := sort.SearchInts(nums, upper)找的是排序数组中第一个大于等于upper的位置。
循环会扫描到r,用于处理upper之前以及上边界附近的空缺。由于前面加入了upper+1哨兵,所以即使upper本身缺失,也能在扫描到upper+1时生成以upper结尾的空缺段。
例子中upper = 12,排序数组中第一个大于等于 12 的元素是 13,所以r = 4。5. 扫描相邻元素,寻找连续空缺段
循环从i = l到i <= r,每次比较nums[i]和nums[i-1]。
如果nums[i] - nums[i-1] > 1,说明这两个相邻的已出现整数之间至少隔了一个整数,因此中间部分全部没有出现在nums中,形成一段连续空缺:
起点是nums[i-1] + 1,终点是nums[i] - 1。
如果差值等于 1,说明两个数连续,没有空缺;如果差值为 0,说明有重复元素,也没有空缺。对例子[0,3,7,9,13]:
• 比较 3 和 0,差为 3,大于 1,空缺为
[1,2];• 比较 7 和 3,差为 4,大于 1,空缺为
[4,6];• 比较 9 和 7,差为 2,大于 1,空缺为
[8,8];• 比较 13 和 9,差为 4,大于 1,空缺为
[10,12]。
6. 收集结果
每发现一个间隔大于 1 的相邻对,就把对应的[起点, 终点]加入答案数组ans。
因为数组已经升序排序,并且扫描方向是从左到右,所以生成的空缺区间天然按起点从小到大排列,不需要再额外排序。
最终得到[[1,2],[4,6],[8,8],[10,12]]。
7. 返回答案
扫描结束后直接返回ans。如果[lower, upper]内没有缺失整数,那么扫描过程中不会产生任何区间,返回空数组。
复杂度分析:
设原始nums的长度为n。加入两个哨兵后长度最多为n+2,仍为O(n)。
• 时间复杂度:
排序需要O(n log n);两次二分查找各需要O(log n);扫描相邻元素最多O(n)。因此总时间复杂度为O(n log n),排序是主要开销。• 额外空间复杂度:
append可能导致新的底层数组分配,最坏需要O(n)额外空间;排序本身是原地排序,但递归栈等辅助空间为O(log n);答案ans在最坏情况下可能包含O(n)个区间。因此总额外空间复杂度为O(n)。如果不把返回结果本身计入辅助空间,则最坏也主要受append扩容影响,为O(n)。
package main
import (
"fmt"
"slices"
"sort"
)
func findDisappearedNumbers(nums []int, lower, upper int) (ans [][]int) {
nums = append(nums, lower-1, upper+1)
slices.Sort(nums)
l := sort.SearchInts(nums, lower+1)
r := sort.SearchInts(nums, upper)
for i := l; i <= r; i++ {
if nums[i]-nums[i-1] > 1 {
ans = append(ans, []int{nums[i-1] + 1, nums[i] - 1})
}
}
return
}
func main() {
nums := []int{3, 9, 7}
lower := 1
upper := 12result := findDisappearedNumbers(nums, lower, upper)
fmt.Println(result)
}
Python完整代码如下:
# -*-coding:utf-8-*-
from bisect import bisect_left
from typing import List
def find_disappeared_numbers(nums: List[int], lower: int, upper: int) -> List[List[int]]:
arr = sorted(nums + [lower - 1, upper + 1])
l = bisect_left(arr, lower + 1)
r = bisect_left(arr, upper)
ans: List[List[int]] = []
for i in range(l, r + 1):
if arr[i] - arr[i - 1] > 1:
ans.append([arr[i - 1] + 1, arr[i] - 1])
return ans
def main():
nums = [3, 9, 7]
lower = 1
upper = 12
result = find_disappeared_numbers(nums, lower, upper)
print(result)if __name__ == "__main__":
main()
C++完整代码如下:
std::vector int >> findDisappearedNumbers(std::vector< int > nums, int lower, int upper) {
nums.push_back(lower - 1 );
nums.push_back(upper + 1 );
std::sort(nums.begin(), nums.end());
int l = std::lower_bound(nums.begin(), nums.end(), lower + 1 ) - nums.begin();
int r = std::lower_bound(nums.begin(), nums.end(), upper) - nums.begin();
std::vector int >> ans;
for ( int i = l; i <= r; ++i) {
if (nums[i] - nums[i - 1 ] > 1 ) {
ans.push_back({nums[i - 1 ] + 1 , nums[i] - 1 });
}
}
return ans;
}
int main() {
std::vector< int > nums = { 3 , 9 , 7 };
int lower = 1 , upper = 12 ;
auto result = findDisappearedNumbers(nums, lower, upper);
std::cout << "[" ;
for (size_t i = 0 ; i < result.size(); ++i) {
std::cout << "[" << result[i][ 0 ] << " " << result[i][ 1 ] << "]" ;
if (i + 1 < result.size()) std::cout << " " ;
}
std::cout << "]" << std::endl;
return 0 ;
}
芯谷ai:xinguhub.com/sign-up?aff=txk5
我们相信人工智能为普通人提供了一种“增强工具”,并致力于分享全方位的AI知识。在这里,您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”,发消息可获得面试资料,让AI助力您的未来发展。
热门跟贴