求问Jane Street一道面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求问Jane Street一道面试题

求问Jane Street一道面试题# JobHunting - 待字闺中

f*l2015-09-22 07:09

1 楼

有个大小为n+1的数组，数组中的每个元素是[1,n]，所以至少有两个是重复的。例如n=
4, 数组为[2,3,4,1,1]或者[2,3,1,1,1]，要求找出重复的那个数字。复杂度要求：空
间O(1), 时间复杂度：小于O(n^2)。不能改变原来数组。
请各位看清题目再回复，和LC的题目不一样。

d*t2015-09-22 07:09

2 楼

XOR?

n=

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

: 有个大小为n+1的数组，数组中的每个元素是[1,n]，所以至少有两个是重复的。例如n=
: 4, 数组为[2,3,4,1,1]或者[2,3,1,1,1]，要求找出重复的那个数字。复杂度要求：空
: 间O(1), 时间复杂度：小于O(n^2)。不能改变原来数组。
: 请各位看清题目再回复，和LC的题目不一样。

f*l2015-09-22 07:09

3 楼

能详细说说吗？

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

: XOR?
:
: n=

d*t2015-09-22 07:09

4 楼

不能，因为我也没做。

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

: 能详细说说吗？

z*s2015-09-22 07:09

5 楼

lc原题

f*l2015-09-22 07:09

6 楼

哪个题目？我觉得不一样，如果有错误，请指正。

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

: lc原题

l*u2015-09-22 07:09

7 楼

＂不能改变原来数组＂，找到以后改回去，可以吗? :)

n=

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

b*h2015-09-22 07:09

8 楼

sum up, then you will get it

n=

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

d*t2015-09-22 07:09

9 楼

靠，考过这么多遍的我竟然都忘了。

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

: sum up, then you will get it
:
: n=

f*l2015-09-22 07:09

10 楼

不行

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

: ＂不能改变原来数组＂，找到以后改回去，可以吗? :)
:
: n=

f*l2015-09-22 07:09

11 楼

看清题目再回答，还有楼下的那位。。。如果数组全是1,1,1,1,1，sum up 有啥用？

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

: sum up, then you will get it
:
: n=

j*32015-09-22 07:09

12 楼

压缩了空间，放宽了时间，感觉一定是divide & conquer，最后答案是O(nlogn)这样。
和xor 或者sum 应该没关系，这俩都是遍历出结果，O(n)时间。
有没有点提示？这个当follow up比较常见吧。

b*b2015-09-22 07:09

13 楼

binary search,
int lowbound = 0, uppbound =n;
int mid = (lowbound + uppbound) / 2;
int countLowHalf=0, countUpperHalf = 0;
now go through the list and count how many in lower half, how many in
upperhalf, and update the low/upper bound to the part which has count > n/2.
since each time we reduce the range by 2, so need longn steps to get to the
bottom, and each step need to loop through the whole array, so it's nlogn.
not sure if there is O(n) algorithm.

n=

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