Teradata and Amazon 面试总结，积攒人品

北美农民 发表于 2014-3-4 12:33
你的case的话， 不需要用额外空间。

{56, 3, 23, 77....}总共2千万个数 范围3-30000003

lhn9021 发表于 2014-3-4 00:05
{56, 3, 23, 77....}总共2千万个数 范围3-30000003

这样每个数放到对应有序的位置就行了，in place, 记录没有出现的位置就行。

n/32的空间复杂度还是n

北美农民 发表于 2014-3-4 13:09
这样每个数放到对应有序的位置就行了，in place, 记录没有出现的位置就行。

n/32的空间复杂度还是n

inplace swap是没问题 不过我觉得你应该考虑一下3kw int的空间是多大

lhn9021 发表于 2014-3-4 00:19
inplace swap是没问题 不过我觉得你应该考虑一下3kw int的空间是多大

啥意思？ in place还要考虑别的啥？

lhn9021 发表于 2014-3-4 00:05
{56, 3, 23, 77....}总共2千万个数 范围3-30000003

我重新看了lz的题目。 1000W个数， 若干个缺失。 我的问题是， 不知道缺失的是哪些怎么找。 你的assumption是每个数有范围， 2千万个数范围3-30000003, 请问这个case是怎么知道哪些是缺失的？

北美农民 发表于 2014-3-4 12:06
一千万个请问你咋知道缺失的那个是哪个啊？  比如原长度为5数组是{1，3，4，5，6}， 现在的数组是{1,5,6} ...

说的对，用anagram的方法显然要更好。

北美农民 发表于 2014-3-4 13:09
这样每个数放到对应有序的位置就行了，in place, 记录没有出现的位置就行。

n/32的空间复杂度还是n

做大数据的，n 和 n/32的区别还是很大的，

tangxukai 发表于 2014-3-4 11:50
做大数据的，n 和 n/32的区别还是很大的，

你怎么知道哪些数缺失了？ 还是数据范围就是1-1000W？ 如果是的话， n/32的空间都不需要

北美农民 发表于 2014-3-5 00:52
你怎么知道哪些数缺失了？ 还是数据范围就是1-1000W？ 如果是的话， n/32的空间都不需要

我在题中忘记讲了，这个数据范围就是假定1 - 1000W. 你是怎么做到n/32空间都不用的？

tangxukai 发表于 2014-3-4 11:56
我在题中忘记讲了，这个数据范围就是假定1 - 1000W. 你是怎么做到n/32空间都不用的？

检查元素i是不是在index [i - 1]上， 如果不是就放到这个位置上, 然后对这个位置上的元素继续迭代这个过程。 最后看如果位置i没有元素 i + 1, 那么i + 1就缺失了。 也是线性的。