1.13 amazon intern电面

nintendodog 发表于 2016-1-14 08:53
lz 这题怎么做的？ 暴力的话不是双层循环 感觉这样大材小用了。
或者是hashset 但是空间又上来了，求解

楼主能把这题题目说清楚一些不？数组元素一共多少个？0-100之间，那顶多102个元素了？我感觉要用XOR做？但又不知道该怎么写。。。

nintendodog 发表于 2016-1-14 08:53
lz 这题怎么做的？ 暴力的话不是双层循环 感觉这样大材小用了。
或者是hashset 但是空间又上来了，求解

LC上有这个题 用binary search 比较预设中间值和实际中间值的大小

补充内容 (2016-1-14 09:13):
艾玛不好意思记错了，那个题是missing number，无视我这个吧

vesalius 发表于 2016-1-14 09:10
LC上有这个题 用binary search 比较预设中间值和实际中间值的大小

补充内容 (2016-1-14 09:13):

请问是哪道题呀，谢谢~

luofeidream 发表于 2016-1-14 09:24
请问是哪道题呀，谢谢~

我记错了，不是那个题……

补充内容 (2016-1-14 09:30):
是contains duplicate，但是方法不是我说的那个，我说那个方法是另一个题的

补充内容 (2016-1-14 09:31):
是contains duplicate，但是方法不是我说的那个，我说那个方法是另一个题的

补充内容 (2016-1-14 09:31):
是contains duplicate，但是方法不是我说的那个，我说那个方法是另一个题的

vesalius 发表于 2016-1-14 09:30
我记错了，不是那个题……

补充内容 (2016-1-14 09:30):

哈哈，我觉得这道题要不牺牲空间要不就牺牲时间。。还有别的做法吗

nintendodog 发表于 2016-1-14 08:53
lz 这题怎么做的？ 暴力的话不是双层循环 感觉这样大材小用了。
或者是hashset 但是空间又上来了，求解

真没什么trick的地方，我首先说了最快的方法就用set记录一下，他说可以，然后写完看过ok就问下一个问题了……都没让我优化

iPhD 发表于 2016-1-14 09:04
楼主能把这题题目说清楚一些不？数组元素一共多少个？0-100之间，那顶多102个元素了？我感觉要用XOR做？ ...

就是给一个数组，里面的数的取值范围在[0,100]。

你说的XOR是用来做找出没有duplicate的那一个数吧？用来解 “其他数都是一对一对出现只有一个数是单独的，找出这个数”这道题的吧

zhan8803705 发表于 2016-1-14 11:45
就是给一个数组，里面的数的取值范围在[0,100]。

你说的XOR是用来做找出没有duplicate的那一个数吧？ ...

LZ你好~~这道题 是不是说 0-100，每个数字都出现了一次，但是有且只有一个数字出现了两次。这样就可以用这些数字的和，减去0-100的和了吧？这样就是O(1)space了。不知道我又没有理解错题意。

liujunlovecs 发表于 2016-1-14 13:54
LZ你好~~这道题 是不是说 0-100，每个数字都出现了一次，但是有且只有一个数字出现了两次。这样就可以用 ...

不是，给的例子是不定长度的数组，数组无序

楼主拿到offer了吗？我也是13号面的正在苦苦的等