首页 > 试题广场 >

给定一个整型数组L，数组长度为n，数组元素取值范围[1,n]

[单选题]

给定一个整型数组L，数组长度为n，数组元素取值范围[1,n],（n>2000)，请问最快速找出一个缺失值的时间复杂度是多少？

查看答案及解析

softwareGxy

数组并非有序，所以只能通过遍历查找，时间复杂度为O(n)

发表于 2020-03-26 11:34:55 回复(0)

格拉摩根键圣

遍历一遍数组求和，然后和完整的不缺数字的期待和相减就能得到缺失的那个数字了，O(n)复杂度

发表于 2020-03-14 19:04:09 回复(3)

福宇乔

俺以为是要将N个元素直接按值存储到数组，这样数组直接就是有序的了，然后就可以二分查找log(n)，题意理解有误，QAQ

发表于 2020-03-15 09:39:39 回复(0)

牛客684836843号

什么叫缺失值？能不能定义一下呢？

发表于 2020-12-26 05:07:19 回复(0)

zbp同学

<p>因为整型数组默认取值是0，而题目要求取值范围是1～n，我感觉缺失值就是0，因此便利一遍就知道缺失值的位置了</p>

发表于 2020-08-20 18:06:06 回复(0)

沈xy

我觉得应该是遍历然后用set存储，再从1-n找set中没有的元素。O(2N)

发表于 2020-04-02 12:01:22 回复(0)

一只特立独行的_猪

所有元素和1~n异或，得缺失值

发表于 2020-04-01 23:55:45 回复(2)

提交观点

问题信息

C++工程师快手 2020 Java工程师

上传者：小小

难度：

7条回答 72收藏 1899浏览

扫一扫，把题目装进口袋