网易首页 > 网易号 > 正文 申请入驻

2026-11-16:找到所有数组中消失的数字Ⅱ。用go语言,给定一个整数序列 nums,并给出闭区间端点 lower 和 upper。把闭区间 [lower, upper

0
分享至

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. 1. 加入边界哨兵
    代码先把lower-1和upper+1追加到nums中。
    这样做的目的是保证即使[lower, upper]的开头或结尾存在空缺,也能通过相邻元素差被发现。
    例如输入nums = [3,9,7]、lower = 1、upper = 12,加入后得到[3,9,7,0,13]。

  2. 2. 对数组排序
    使用slices.Sort(nums)将数组升序排序。
    排序后,数组中相邻元素之间的“空隙”就对应可能缺失的整数段。
    上述例子排序后为[0,3,7,9,13]。

  3. 3. 二分查找扫描范围左端点
    l := sort.SearchInts(nums, lower+1)找的是排序数组中第一个大于等于lower+1的位置。
    这个位置之前的相邻差主要涉及lower之前的数,不需要生成结果;从l开始检查,可以覆盖lower附近可能缺失的区间。
    例子中lower+1 = 2,排序数组中第一个大于等于 2 的元素是 3,所以l = 1。

  4. 4. 二分查找扫描范围右端点
    r := sort.SearchInts(nums, upper)找的是排序数组中第一个大于等于upper的位置。
    循环会扫描到r,用于处理upper之前以及上边界附近的空缺。由于前面加入了upper+1哨兵,所以即使upper本身缺失,也能在扫描到upper+1时生成以upper结尾的空缺段。
    例子中upper = 12,排序数组中第一个大于等于 12 的元素是 13,所以r = 4。

  5. 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)。

Go完整代码如下:

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 := 12

result := 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助力您的未来发展。

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
何家劲痛骂移民老友!卖光香港家产去往加拿大,如今哭着说回不来

何家劲痛骂移民老友!卖光香港家产去往加拿大,如今哭着说回不来

人文思辨社
2026-11-16 18:52:29
中国股市大局已定:若一切正常,明年起,中国股市或迎来5大洗牌

中国股市大局已定:若一切正常,明年起,中国股市或迎来5大洗牌

星语者056
2026-11-17 08:46:25
贺子珍始终认定朱道来是战乱之中失散的儿子,可朱道来后来坦言:过去他没有说出所有真相

贺子珍始终认定朱道来是战乱之中失散的儿子,可朱道来后来坦言:过去他没有说出所有真相

磊子讲史
2026-09-16 15:28:05
黄乐最新私密照爆出, 难怪黄仁勋把持不住!

黄乐最新私密照爆出, 难怪黄仁勋把持不住!

仕道
2026-11-17 11:11:01
AI演员一句“戴了一天很舒服”,被罚6.8万元

AI演员一句“戴了一天很舒服”,被罚6.8万元

凤凰网财经
2026-11-17 00:22:30
79岁路都走不稳还开演唱会捞金,全网恶评如潮,她却扬言回馈粉丝

79岁路都走不稳还开演唱会捞金,全网恶评如潮,她却扬言回馈粉丝

背包旅行
2026-11-17 12:11:31
首位来访的国家元首,已经抵达深圳,央视画面中还有5架伊尔-76

首位来访的国家元首,已经抵达深圳,央视画面中还有5架伊尔-76

墨兰史书
2026-11-17 13:15:10
上海1300万多选民投票选举区和乡镇两级人大代表,陈吉宁朱忠明等参加投票

上海1300万多选民投票选举区和乡镇两级人大代表,陈吉宁朱忠明等参加投票

上观新闻
2026-11-16 18:43:28
薇娅找了个好老公,东南亚的生意做大了,一年入账 34 亿

薇娅找了个好老公,东南亚的生意做大了,一年入账 34 亿

起点财经
2026-11-17 08:46:25
谁才是英伟达真正的主人?一张图看懂股东结构

谁才是英伟达真正的主人?一张图看懂股东结构

互联网大观
2026-11-17 15:16:16
央视现场调查证实,当地被迫承认问题;观点:如果基层连基本的实事求是都做不到,那互动也就没有意义

央视现场调查证实,当地被迫承认问题;观点:如果基层连基本的实事求是都做不到,那互动也就没有意义

南方都市报
2026-11-17 08:27:50
加沙影业又穿帮了?

加沙影业又穿帮了?

历史总在押韵
2026-11-17 05:43:54
疑似用虾滑充当肿瘤?中南大学湘雅二医院被爆出史诗级全AI论文

疑似用虾滑充当肿瘤?中南大学湘雅二医院被爆出史诗级全AI论文

西虹市闲话
2026-11-16 18:42:42
尹国良,在广州逝世

尹国良,在广州逝世

南方都市报
2026-11-17 11:56:38
男子被熟人骗至缅甸电诈园区,姐姐赴泰国营救

男子被熟人骗至缅甸电诈园区,姐姐赴泰国营救

网易新闻出品
2026-11-16 18:25:30
雷军现身APEC会议现场

雷军现身APEC会议现场

每日经济新闻
2026-11-17 15:48:37
4岁藏族小女孩牵着高反女游客找氧气:“别哭了,哭的话会越来越缺氧”

4岁藏族小女孩牵着高反女游客找氧气:“别哭了,哭的话会越来越缺氧”

一丝不苟的法律人
2026-11-15 17:01:02
自研Agent两场实测均分超过GPT-6,NovaSilicon首提CDK,Fabless之后是Designless?

自研Agent两场实测均分超过GPT-6,NovaSilicon首提CDK,Fabless之后是Designless?

机器之心Pro
2026-11-16 14:36:30
西安女大学生被系书记猥亵,不堪折磨上吊自尽,遗书内容曝光

西安女大学生被系书记猥亵,不堪折磨上吊自尽,遗书内容曝光

夜话奇谭
2026-11-17 13:37:52
记者惊呼Amazing APEC媒体包都有啥?

记者惊呼Amazing APEC媒体包都有啥?

看看新闻Knews
2026-11-17 14:08:28
2026-11-17 16:15:00
moonfdd incentive-icons
moonfdd
福大大架构师每日一题
1580文章数 83关注度
往期回顾 全部

科技要闻

硅谷大佬组局,帮黄仁勋杀回来!

头条要闻

中国女子在希腊失踪半年 保险箱发现10万欧元现金

头条要闻

中国女子在希腊失踪半年 保险箱发现10万欧元现金

体育要闻

伪强队?拥4亿豪阵欧国联6连败+世界杯出局

娱乐要闻

陈晓楠对话厉娜和许飞引全网热议

财经要闻

10万人逼宫英伟达,黄仁勋要复职了?

汽车要闻

更豪华更好开 问界新M8细节升级见真章

态度原创

游戏
手机
旅游
家居
公开课

小伙表示连玩7天《GTA6》 这下PS5可惨了

手机要闻

鞠婧祎代言 荣耀700系列四款高颜值配色公布:全系标配原生AI背屏

旅游要闻

秋假遛娃剑门关,全程17000步,6个小时,喜提废腿体验!

家居要闻

2026建博会(广州) 公装联探展交流活动

公开课

李玫瑾:为什么性格比能力更重要?

无障碍浏览 进入关怀版