我的前半生到底要表现出什么逻辑 - 未名空间MITBBS历史存档

我的前半生到底要表现出什么逻辑# TVChinese - 中文电视

h*t2017-07-27 07:07

1 楼

两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b，把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
还是希望能拿到on site...
——————————————————————————
应该算很简单的，我实在是比较水，学艺不精：
1) a big array with a thousand elements storing integers from 1 to 1000, not
sorted. One number is duplicated. How do you find the duplicated number
most efficiently.
2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
. one number is missing in the array. How do you find that missing number in
the most efficient way.
想听听大家的法子，学习学习。晚些时候我来更新interviewer 给我的答案。

B*y2017-07-27 07:07

2 楼

因为行程变动，本来晚上7点的飞机，因为客户需要在同一时间见面，只能提前坐1点的
飞机。去网上看改时间要交$150的改票费。如果我直接去机场等，是不是可以直接改票
而不用交改票费？貌似当天还有很多航班没有卖出。

m*l2017-07-27 07:07

3 楼

我保存到精华区了,不是故意删除,
有人提到说一下

w*r2017-07-27 07:07

4 楼

说是Your Response is Required By Law。大家有收到过吗？

b*82017-07-27 07:07

5 楼

这个我的前半生终于放完了，本来是一部女人励志的片子。结果搞出这种结尾，真特么
的不知道导演还是编剧谁特么的脑子坏了。这部电视剧到底是要讲什么的，结尾一出更
让人看不懂了。
你说是讲罗子君的奋斗史，可是罗子君最后得到了什么，结尾并不好，她暧昧和思念的
对象居然是闺蜜多年的男友，这种结局可以称得上是完美么。为了别人的事情两肋插刀
的贺函，最后又怎么样，变成了一个在海边的卖鱼人。
而一个机关算尽，坑蒙害人无数的小三邻凌居然最后却没有受到任何损失，和他那个没
长眼睛的罗子君的前夫一起飞黄腾达了，感情也没受到影响。
这部电视剧到底要讲什么内容，太荒诞了，逻辑非常混乱，不知道要怎么表现剧中的一
个中心思想。包括老卓也是，他们到了最后都突然消失了，不知道要表现出一个什么意
思。

f*g2017-07-27 07:07

6 楼

确实经典。
不过第一题是不是描述的有点问题：
既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？

p*r2017-07-27 07:07

7 楼

http://www.united.com/web/en-US/content/reservations/samedaycha

【在 B******y 的大作中提到】

: 因为行程变动，本来晚上7点的飞机，因为客户需要在同一时间见面，只能提前坐1点的
: 飞机。去网上看改时间要交$150的改票费。如果我直接去机场等，是不是可以直接改票
: 而不用交改票费？貌似当天还有很多航班没有卖出。

H*i2017-07-27 07:07

8 楼

-----

e*t2017-07-27 07:07

9 楼

没有

【在 w********r 的大作中提到】

: 说是Your Response is Required By Law。大家有收到过吗？

y*a2017-07-27 07:07

10 楼

真的蛮恶心的，看完跟吃了苍蝇似的感觉，这都啥玩意
这编剧三观绝对有问题的

【在 b****8 的大作中提到】

: 这个我的前半生终于放完了，本来是一部女人励志的片子。结果搞出这种结尾，真特么
: 的不知道导演还是编剧谁特么的脑子坏了。这部电视剧到底是要讲什么的，结尾一出更
: 让人看不懂了。
: 你说是讲罗子君的奋斗史，可是罗子君最后得到了什么，结尾并不好，她暧昧和思念的
: 对象居然是闺蜜多年的男友，这种结局可以称得上是完美么。为了别人的事情两肋插刀
: 的贺函，最后又怎么样，变成了一个在海边的卖鱼人。
: 而一个机关算尽，坑蒙害人无数的小三邻凌居然最后却没有受到任何损失，和他那个没
: 长眼睛的罗子君的前夫一起飞黄腾达了，感情也没受到影响。
: 这部电视剧到底要讲什么内容，太荒诞了，逻辑非常混乱，不知道要怎么表现剧中的一
: 个中心思想。包括老卓也是，他们到了最后都突然消失了，不知道要表现出一个什么意

r*l2017-07-27 07:07

11 楼

这个这个：全加起来再和sum(1:999)比。
In the 2nd problem, looks like 1000-2 elements, or 1000 is stored.

not
sorted
in

【在 h**t 的大作中提到】

: 两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b，把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
: 还是希望能拿到on site...
: ——————————————————————————
: 应该算很简单的，我实在是比较水，学艺不精：
: 1) a big array with a thousand elements storing integers from 1 to 1000, not
: sorted. One number is duplicated. How do you find the duplicated number
: most efficiently.
: 2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
: . one number is missing in the array. How do you find that missing number in
: the most efficient way.

m*l2017-07-27 07:07

12 楼

你的贴子和图都在精华区里面

【在 H******i 的大作中提到】

: -----

h*t2017-07-27 07:07

13 楼

这两个题分开来看的，第一个题只是要找出重复的那个数

【在 f***g 的大作中提到】

: 确实经典。
: 不过第一题是不是描述的有点问题：
: 既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？

h*t2017-07-27 07:07

14 楼

赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
redBull啊。。。是cs,ee背景的？
第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
的间接方法...

【在 r*****l 的大作中提到】

: 这个这个：全加起来再和sum(1:999)比。
: In the 2nd problem, looks like 1000-2 elements, or 1000 is stored.
:
: not
: sorted
: in

s*n2017-07-27 07:07

15 楼

楼主,把他给你的algorithm分享一下吧?

r*l2017-07-27 07:07

16 楼

第二道题也是一样的做法。
其实我想很多人都知道答案的。只不过他们没时间回答或还没看到你的贴子。

【在 h**t 的大作中提到】

: 赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
: redBull啊。。。是cs,ee背景的？
: 第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
: 的间接方法...

A*n2017-07-27 07:07

17 楼

N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了.

not
sorted
in

【在 h**t 的大作中提到】

: 赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
: redBull啊。。。是cs,ee背景的？
: 第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
: 的间接方法...

s*y2017-07-27 07:07

18 楼

N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了.

s*y2017-07-27 07:07

19 楼

第2题，careercup 150上面有，把1000 pack到1024个number
就是pack 1001， 1002 。。。1024 number上去
然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。

h*t2017-07-27 07:07

20 楼

很谦虚阿。。。

【在 r*****l 的大作中提到】

: 第二道题也是一样的做法。
: 其实我想很多人都知道答案的。只不过他们没时间回答或还没看到你的贴子。

h*t2017-07-27 07:07

21 楼

我一会儿的。。。先看看大家的做法

【在 s*****n 的大作中提到】

: 楼主,把他给你的algorithm分享一下吧?

h*t2017-07-27 07:07

22 楼

看来是我复习的不到家。。。嗯哪里能找到这些面试题？精华区？careercup?

【在 A*********n 的大作中提到】

: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
:
: not
: sorted
: in

h*t2017-07-27 07:07

23 楼

你的做法根面试的人给我的方法有些像，他给我的更好理解些。

【在 s*****y 的大作中提到】

: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.

r*r2017-07-27 07:07

24 楼

这个方法还挺巧的，相当于不用额外空间记录了各个数都出现过没有

【在 s*****y 的大作中提到】

: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.

h*t2017-07-27 07:07

25 楼

我。。。不明白。。。什莫是xor?

【在 s*****y 的大作中提到】

: 第2题，careercup 150上面有，把1000 pack到1024个number
: 就是pack 1001， 1002 。。。1024 number上去
: 然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。

i*d2017-07-27 07:07

26 楼

这样做worst cast cost是多少？

【在 s*****y 的大作中提到】

: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.

r*y2017-07-27 07:07

27 楼

异或 ^
半路出家的?

【在 h**t 的大作中提到】

: 我。。。不明白。。。什莫是xor?

s*y2017-07-27 07:07

28 楼

worst case is walk through the whole array.
O(n)

【在 i*********d 的大作中提到】

: 这样做worst cast cost是多少？

h*t2017-07-27 07:07

29 楼

受鄙视了〉_<

【在 r***y 的大作中提到】

: 异或 ^
: 半路出家的?

r*y2017-07-27 07:07

30 楼

木有, 随手一问

【在 h**t 的大作中提到】

: 受鄙视了〉_<

r*l2017-07-27 07:07

31 楼

You need to do more homework. XOR is exclusive OR.
for binary:
0 xor 0 = 1 xor 1 = 0
0 xor 1 = 1 xor 0 = 1
For any number a: a xor a = 0.
For any number a, b: a xor b xor b = a
Basically, as long as you see a variable appears even # of times in a xor
relationship, you can ignore it.
Very useful during interview.

【在 h**t 的大作中提到】

: 我。。。不明白。。。什莫是xor?

s*y2017-07-27 07:07

32 楼

是啊，这题一般都是刚开始的开胃小菜吧

【在 s*****y 的大作中提到】

: 第2题，careercup 150上面有，把1000 pack到1024个number
: 就是pack 1001， 1002 。。。1024 number上去
: 然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。

b*g2017-07-27 07:07

33 楼

我想第一题应该是1001个elements

【在 f***g 的大作中提到】

: 确实经典。
: 不过第一题是不是描述的有点问题：
: 既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？

n*t2017-07-27 07:07

34 楼

我觉得也是

【在 b*******g 的大作中提到】

: 我想第一题应该是1001个elements

p*92017-07-27 07:07

35 楼

should classify them as brainteaser problem, not algorithm problem.

y*m2017-07-27 07:07

36 楼

俺觉得考这种题对一个训练有数的人很简单吧？对第一次碰到的人就要考量考量。
结论：这种题没有太多区分度....

求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b，把
a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都
check，如果已经有1存入就
not
sorted
in

【在 h**t 的大作中提到】

: 两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b，把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
: 还是希望能拿到on site...
: ——————————————————————————
: 应该算很简单的，我实在是比较水，学艺不精：
: 1) a big array with a thousand elements storing integers from 1 to 1000, not
: sorted. One number is duplicated. How do you find the duplicated number
: most efficiently.
: 2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
: . one number is missing in the array. How do you find that missing number in
: the most efficient way.

s*z2017-07-27 07:07

37 楼

这道题正是我用来面试人的算法题啊. 可是面试了那么多人, 没有一个给出这个XOR算
法的. 对于高速ASIC设计来说, XOR算法最好, 没有CARRY-CHAIN, 可以并行处理, 而且
不需要额外的STORAGE.

b*82017-07-27 07:07

38 楼

先看看异或，再看看加。不行再问问，哈希、位图这些行不行，额外空间有多少，到这
里基本就出来了。实在不行就In Place排序了。这套思路可以解决不少题目，至少有的
跟他扯蛋半天，不会哑场。

h*t2017-07-27 07:07

39 楼

两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b，把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
还是希望能拿到on site...
——————————————————————————
应该算很简单的，我实在是比较水，学艺不精：
1) a big array with a thousand elements storing integers from 1 to 1000, not
sorted. One number is duplicated. How do you find the duplicated number
most efficiently.
2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
. one number is missing in the array. How do you find that missing number in
the most efficient way.
想听听大家的法子，学习学习。晚些时候我来更新interviewer 给我的答案。

f*g2017-07-27 07:07

40 楼

确实经典。
不过第一题是不是描述的有点问题：
既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？

r*l2017-07-27 07:07

41 楼

这个这个：全加起来再和sum(1:999)比。
In the 2nd problem, looks like 1000-2 elements, or 1000 is stored.

not
sorted
in

【在 h**t 的大作中提到】

: 两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b，把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
: 还是希望能拿到on site...
: ——————————————————————————
: 应该算很简单的，我实在是比较水，学艺不精：
: 1) a big array with a thousand elements storing integers from 1 to 1000, not
: sorted. One number is duplicated. How do you find the duplicated number
: most efficiently.
: 2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
: . one number is missing in the array. How do you find that missing number in
: the most efficient way.

h*t2017-07-27 07:07

42 楼

这两个题分开来看的，第一个题只是要找出重复的那个数

【在 f***g 的大作中提到】

: 确实经典。
: 不过第一题是不是描述的有点问题：
: 既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？

h*t2017-07-27 07:07

43 楼

赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
redBull啊。。。是cs,ee背景的？
第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
的间接方法...

【在 r*****l 的大作中提到】

: 这个这个：全加起来再和sum(1:999)比。
: In the 2nd problem, looks like 1000-2 elements, or 1000 is stored.
:
: not
: sorted
: in

s*n2017-07-27 07:07

44 楼

楼主,把他给你的algorithm分享一下吧?

r*l2017-07-27 07:07

45 楼

第二道题也是一样的做法。
其实我想很多人都知道答案的。只不过他们没时间回答或还没看到你的贴子。

【在 h**t 的大作中提到】

: 赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
: redBull啊。。。是cs,ee背景的？
: 第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
: 的间接方法...

A*n2017-07-27 07:07

46 楼

N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了.

not
sorted
in

【在 h**t 的大作中提到】

: 赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
: redBull啊。。。是cs,ee背景的？
: 第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
: 的间接方法...

s*y2017-07-27 07:07

47 楼

N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了.
---------------------------------
你这样子就是一定要遍历n个element，我记得经典做法是
假设array是A[0]----A[5]
array是 2，1，1，0，4，3
A[0] = 2，把A[0]和A[2]换，array变成 1， 1， 2， 0， 4， 3
如何A[i]=i，就可以跳过，继续看A[0]， A[0]=1， detect到A[1]已经有1了，
找到Duplicate是1。
我这里number从0开始，从1开始的数稍微改动一下。

s*y2017-07-27 07:07

48 楼

第2题，careercup 150上面有，把1000 pack到1024个number
就是pack 1001， 1002 。。。1024 number上去
然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。

h*t2017-07-27 07:07

49 楼

很谦虚阿。。。

【在 r*****l 的大作中提到】

: 第二道题也是一样的做法。
: 其实我想很多人都知道答案的。只不过他们没时间回答或还没看到你的贴子。

h*t2017-07-27 07:07

50 楼

我一会儿的。。。先看看大家的做法

【在 s*****n 的大作中提到】

: 楼主,把他给你的algorithm分享一下吧?

h*t2017-07-27 07:07

51 楼

看来是我复习的不到家。。。嗯哪里能找到这些面试题？精华区？careercup?

【在 A*********n 的大作中提到】

: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
:
: not
: sorted
: in

h*t2017-07-27 07:07

52 楼

你的做法根面试的人给我的方法有些像，他给我的更好理解些。

【在 s*****y 的大作中提到】

: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
: ---------------------------------
: 你这样子就是一定要遍历n个element，我记得经典做法是
: 假设array是A[0]----A[5]
: array是 2，1，1，0，4，3
: A[0] = 2，把A[0]和A[2]换，array变成 1， 1， 2， 0， 4， 3
: 如何A[i]=i，就可以跳过，继续看A[0]， A[0]=1， detect到A[1]已经有1了，
: 找到Duplicate是1。
: 我这里number从0开始，从1开始的数稍微改动一下。

r*r2017-07-27 07:07

53 楼

这个方法还挺巧的，相当于不用额外空间记录了各个数都出现过没有

【在 s*****y 的大作中提到】

: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
: ---------------------------------
: 你这样子就是一定要遍历n个element，我记得经典做法是
: 假设array是A[0]----A[5]
: array是 2，1，1，0，4，3
: A[0] = 2，把A[0]和A[2]换，array变成 1， 1， 2， 0， 4， 3
: 如何A[i]=i，就可以跳过，继续看A[0]， A[0]=1， detect到A[1]已经有1了，
: 找到Duplicate是1。
: 我这里number从0开始，从1开始的数稍微改动一下。

h*t2017-07-27 07:07

54 楼

我。。。不明白。。。什莫是xor?

【在 s*****y 的大作中提到】

: 第2题，careercup 150上面有，把1000 pack到1024个number
: 就是pack 1001， 1002 。。。1024 number上去
: 然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。

i*d2017-07-27 07:07

55 楼

这样做worst cast cost是多少？

【在 s*****y 的大作中提到】

: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
: ---------------------------------
: 你这样子就是一定要遍历n个element，我记得经典做法是
: 假设array是A[0]----A[5]
: array是 2，1，1，0，4，3
: A[0] = 2，把A[0]和A[2]换，array变成 1， 1， 2， 0， 4， 3
: 如何A[i]=i，就可以跳过，继续看A[0]， A[0]=1， detect到A[1]已经有1了，
: 找到Duplicate是1。
: 我这里number从0开始，从1开始的数稍微改动一下。

r*y2017-07-27 07:07

56 楼

异或 ^
半路出家的?

【在 h**t 的大作中提到】

: 我。。。不明白。。。什莫是xor?

s*y2017-07-27 07:07

57 楼

worst case is walk through the whole array.
O(n)

【在 i*********d 的大作中提到】

: 这样做worst cast cost是多少？

h*t2017-07-27 07:07

58 楼

受鄙视了〉_<

【在 r***y 的大作中提到】

: 异或 ^
: 半路出家的?

r*y2017-07-27 07:07

59 楼

木有, 随手一问

【在 h**t 的大作中提到】

: 受鄙视了〉_<

r*l2017-07-27 07:07

60 楼

You need to do more homework. XOR is exclusive OR.
for binary:
0 xor 0 = 1 xor 1 = 0
0 xor 1 = 1 xor 0 = 1
For any number a: a xor a = 0.
For any number a, b: a xor b xor b = a
Basically, as long as you see a variable appears even # of times in a xor
relationship, you can ignore it.
Very useful during interview.

【在 h**t 的大作中提到】

: 我。。。不明白。。。什莫是xor?

s*y2017-07-27 07:07

61 楼

是啊，这题一般都是刚开始的开胃小菜吧

【在 s*****y 的大作中提到】

: 第2题，careercup 150上面有，把1000 pack到1024个number
: 就是pack 1001， 1002 。。。1024 number上去
: 然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。

b*g2017-07-27 07:07

62 楼

我想第一题应该是1001个elements

【在 f***g 的大作中提到】

: 确实经典。
: 不过第一题是不是描述的有点问题：
: 既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？

n*t2017-07-27 07:07

63 楼

我觉得也是

【在 b*******g 的大作中提到】

: 我想第一题应该是1001个elements

p*92017-07-27 07:07

64 楼

should classify them as brainteaser problem, not algorithm problem.

y*m2017-07-27 07:07

65 楼

俺觉得考这种题对一个训练有数的人很简单吧？对第一次碰到的人就要考量考量。
结论：这种题没有太多区分度....

求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b，把
a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都
check，如果已经有1存入就是br />
not
sorted
in

【在 h**t 的大作中提到】

: 两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b，把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
: 还是希望能拿到on site...
: ——————————————————————————
: 应该算很简单的，我实在是比较水，学艺不精：
: 1) a big array with a thousand elements storing integers from 1 to 1000, not
: sorted. One number is duplicated. How do you find the duplicated number
: most efficiently.
: 2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
: . one number is missing in the array. How do you find that missing number in
: the most efficient way.

s*z2017-07-27 07:07

66 楼

这道题正是我用来面试人的算法题啊. 可是面试了那么多人, 没有一个给出这个XOR算
法的. 对于高速ASIC设计来说, XOR算法最好, 没有CARRY-CHAIN, 可以并行处理, 而且
不需要额外的STORAGE.

b*82017-07-27 07:07

67 楼

先看看异或，再看看加。不行再问问，哈希、位图这些行不行，额外空间有多少，到这
里基本就出来了。实在不行就In Place排序了。这套思路可以解决不少题目，至少有的
跟他扯蛋半天，不会哑场。

Y*B2017-07-27 07:07

68 楼

如果第一题按照原题意，1000个元素有一个是重复的，那么你们的加加减减的方法根本
不好使。面试管的答案才是他的题目的正解。
注意审题！！

a*n2017-07-27 07:07

69 楼

同样有这个问题i,如果是这样的话，就不能用求和的方法做了吧。

【在 f***g 的大作中提到】

: 确实经典。
: 不过第一题是不是描述的有点问题：
: 既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？

k*n2017-07-27 07:07

70 楼

这题做法很多，只知道一种显然是不够的

【在 s*****y 的大作中提到】

: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
: ---------------------------------
: 你这样子就是一定要遍历n个element，我记得经典做法是
: 假设array是A[0]----A[5]
: array是 2，1，1，0，4，3
: A[0] = 2，把A[0]和A[2]换，array变成 1， 1， 2， 0， 4， 3
: 如何A[i]=i，就可以跳过，继续看A[0]， A[0]=1， detect到A[1]已经有1了，
: 找到Duplicate是1。
: 我这里number从0开始，从1开始的数稍微改动一下。