yelp 店面

我猜因该是跪了....这题最佳解 我没做出来 给一个array 已知element ranges 是1 to N 然后array s

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

的solution 瓒人品 球pass... 求好的solution....

say543 发表于 2016-1-31 12:12
有先考trade off的solution 最后这个没解出来的 是希望在constraint 的情况下达成 先不用考虑time comp ...

O(n^2)的方法吗？两个for循环就行了吧
for i=0:N-2
  for j=i+1:N-1
    if(arr[i]==arr[j]) return arr[i]

正在看楼下那个题目别人的解答，或许可行：https://leetcode.com/discuss/615 ... difying-explanation

googlerr 发表于 2016-1-31 10:52
O(n^2) 可以，不过如果是为了追求空间小而无视时间，那这题也太没意义了

有先考trade off的solution 最后这个没解出来的 是希望在constraint 的情况下达成 先不用考虑time complexity 能分享怎么做吗 ?

googlerr 发表于 2016-1-30 11:34
有两点不完全明白：还可能有多个数字重复出现？比如[1,1,2,2]？另外，可能出现2次以上？如[1,1,1,2,2]。如 ...

[1,1,2,2]
输出1 or 2都可
[1,1,1,2,2]
输出1 or 2都可

两个case都符合题意
要求真的是要o(1) space 且不能改array...

有两点不完全明白：还可能有多个数字重复出现？比如[1,1,2,2]？另外，可能出现2次以上？如[1,1,1,2,2]。如果这两个都成立，还能有O(1) space且不改array的方法吗？

o(n) time?怎么感觉不太可能。。。

https://leetcode.com/problems/find-the-duplicate-number/

楼主是怎么拿到的面试？网申还是内推的？

tltzhsajsdr 发表于 2016-1-30 15:43
https://leetcode.com/problems/find-the-duplicate-number/

好像不完全一样。这里可能有多个duplicate，LC上只有一个

觉得理论上不可行啊，不改content觉得不能符合要求，很明确说了不能修改这个array么？

Xochitl 发表于 2016-1-31 10:19
觉得理论上不可行啊，不改content觉得不能符合要求，很明确说了不能修改这个array么？

O(n^2) 可以，不过如果是为了追求空间小而无视时间，那这题也太没意义了