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

北美农民 发表于 2014-3-5 01:02
检查元素i是不是在index 上， 如果不是就放到这个位置上, 然后对这个位置上的元素继续迭代这个过程。 最后 ...

我想在一个未排序的数组里。
我不知道是不是我没理解你的意思：
第一点，原来在i-1位置上的数字怎么办，你的方法好像会覆盖原来的值呢。你的意思好像是将i和在i-1位置上的数据交换，这样你怎么得知数据i原来在哪里？不用搜索吗？
第二点，因为是缺失任意个数据，现在假如数组为
[1,2,4,6]。3和5没有了，你的解法是不是不合适了？

tangxukai 发表于 2014-3-4 12:15
我想在一个未排序的数组里。
我不知道是不是我没理解你的意思：
第一点，原来在i-1位置上的数 ...

i放到i-1上， 原来i-1位置上得数是a[ i - 1 ]那么继续看a[ a[i - 1] - 1]上是不是a[i - 1] 不是又放过去。 这么迭代。

你这个例子，1在index 0不用管， 2在index 1不用管， 4在 index 2上有问题， 然后找到a[4 - 1] = 6覆盖上去， 然后6大于数组长度了不用理了。 这样数组变成了{1,2,4,4}, 然后发现3不在index2上， 于是缺了3.

这个例子本来也不好 是因为你的题目是1000w长度的数组放1-1000W。

北美农民 发表于 2014-3-5 01:48
i放到i-1上， 原来i-1位置上得数是a[ i - 1 ]那么继续看a[ a - 1]上是不是a 不是又放过去。 这么迭代。
...

good，明白了。

北美农民 发表于 2014-3-5 01:48
i放到i-1上， 原来i-1位置上得数是a[ i - 1 ]那么继续看a[ a - 1]上是不是a 不是又放过去。 这么迭代。
...

这种类似leetcode find first missing positive 的解法只能得到第一个missing

lhn9021 发表于 2014-3-4 13:53
这种类似leetcode find first missing positive 的解法只能得到第一个missing

不会， 扫两遍就是了。

北美农民 发表于 2014-3-5 02:55
不会， 扫两遍就是了。

如果给的数组大小是2million 范围是3million 你怎么swap 保证结果正确

lhn9021 发表于 2014-3-4 14:03
如果给的数组大小是2million 范围是3million 你怎么swap 保证结果正确

你得先告诉我你这个case你怎么知道哪些数遗失了？ 我不明白。

楼主是n个坑放范围为1-n的n个数， original data set已知， 所以我能知道哪些遗失了。 你的case如何知道哪些数丢失了？

我知道范围是从多少到多少 我知道original data set为什么找不出哪些丢失？ 为什么你说是n 个坑放1-n n个数？坑是数组大小？ 如果有missing number的话 坑肯定小于取值范围啊 这样swap不就做不了了吗

lhn9021 发表于 2014-3-4 14:11
我知道范围是从多少到多少 我知道original data set为什么找不出哪些丢失？ 为什么你说是n 个坑放1-n n个数 ...

因为楼主的题目就是n个坑放范围为1-n的n个数， 我当然要问清楚面经的题意啊。

开始我以为你是楼主， 所以跟着你的条件看了一下发现原来你是自己的假设而已。楼主的条件是缺失了几个， 你的case是 300W个数放100W的坑里， 一下缺失了200W个。

北美农民 发表于 2014-3-5 03:05
你得先告诉我你这个case你怎么知道哪些数遗失了？ 我不明白。

楼主是n个坑放范围为1-n的n个数， origi ...

你的理解是不是1million是range不是数组大小啊？ 我的理解1million是数组大小不是range