一个算法问题

2009/12/6镜像同步55 回复

一个数组num[n]; n为已知数，可能很大数组中的数大小为0~n，且不重复，因此数组中包含0~n这n+1个数中的n个要求找出数组中没有的那个数显然排序后查找可以满足，但是时间为O(nlgn) 想知道有没有更快的方法，n可能很大，所以空间占用不能太大，要求至少小于O(n)

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

jmpesp机器人#1 · 2009/12/6

【在 DarkIce 的大作中提到: 】 : 一个数组num[n]; n为已知数，可能很大 : 数组中的数大小为0~n，且不重复，因此数组中包含0~n这n+1个数中的n个 : 要求找出数组中没有的那个数 : ................... o（n）可以解决，不过空间也是o（n）不知道谁还有更好的解法

he1l0机器人#2 · 2009/12/6

先把一个变量，比如m赋值为0～n，n+1个数的xor，再去xor数组里的每个元素，最后得到的就是缺的那个，嗯，好象是这样

jmpesp机器人#3 · 2009/12/6

【在 he1l0 的大作中提到: 】 : 先把一个变量，比如m赋值为0～n，n+1个数的xor，再去xor数组里的每个元素，最后得到的就是缺的那个，嗯，好象是这样你这个最坏时间复杂度都o(n^2)

wifil机器人#4 · 2009/12/6

任取x a = x; for i <- 0 to n+1 x ^= i for i <- 0 to n x ^= num[i] x ^= a 此时x = 缺少的数

coolwc机器人#5 · 2009/12/6

n(n+1)/2 - sum(array) = the lost number

he1l0机器人#6 · 2009/12/6

时间复杂度O（n），空间复杂度O（1），用xor是怕溢出，本意是用+法，求0～n，n+1个数的和，在把数组中的每个数减去，得到的就是缺的那个数【在 jmpesp 的大作中提到: 】 : 你这个最坏时间复杂度都o(n^2)

coolwc机器人#7 · 2009/12/6

扩展性差点题目变成缺失两个数如何？【在 he1l0 的大作中提到: 】 : 先把一个变量，比如m赋值为0～n，n+1个数的xor，再去xor数组里的每个元素，最后得到的就是缺的那个，嗯，好象是这样

jmpesp机器人#8 · 2009/12/6

【在 he1l0 的大作中提到: 】 : 时间复杂度O（n），空间复杂度O（1），用xor是怕溢出，本意是用+法，求0～n，n+1个数的和，在把数组中的每个数减去，得到的就是缺的那个数哦，我理解错了，学习一下~~

PtwCJ机器人#9 · 2009/12/6

re 【在 coolwc (小包) 的大作中提到: 】 : n(n+1)/2 - sum(array) = the lost number