Google Phone Interview

能问一下 第一题关于 duplicate有更多条件么?
比如说 只有一个数字出现了两次, 其他数字都只出现一次
或者说 任意多个数字出现两次, 其他数字只出现一次
还是说 任意数字出现任意多次?
多谢了

怎么做到的O(1)??

MrQuin33 发表于 2019-5-21 00:30
能问一下 第一题关于 duplicate有更多条件么?
比如说 只有一个数字出现了两次, 其他数字都只出现一次
或 ...

如果是那样的话，很想leetcode上的一道题，通过XOR 所有的数即可，但是也要 O(n)

不管怎么样，所有数都得找一遍吧，不理解怎么会有O(1）O（1）的算法。。。如果是只有一个Duplicate number，就把所有数的和减去(1+N)*N/2就可以了。如果是多个duplicate numbers，肯定需要个额外list输出结果吧。。。。

第一题应该是不能优化了吧。LZ做的没问题，除非他给的是sorted array.
第二题应该就是bfs吧...说着是爬虫感觉也没问题。。

补充内容 (2019-5-21 03:37):
求波米~

linjjyy 发表于 2019-5-20 02:24
不好意思打错了，是nlogn。Google挂了会冻一年吧。。挂了只能看社招有没机会了

phone screen 也会冻一年吗
不是说onsite挂了冻一年？

如果我没理解错的话，第一题array里的abs(数字)-1作为index，然后将该index对应的值变成负的，每一次映射之前都检查是不是负的，是就是dup，这不是LC上的原题么？还是我看漏了东西？

补充内容 (2019-5-21 04:59):
不过时间复杂度O(1)是认真的？

O(1) 时间复杂度我认为不可能实现, 最坏情况必须得看到所有元素才可以确定谁重复了

O(1)时间复杂度真的可以嘛。。。

最佳应该是时间复杂度O（n）和空间复杂度O（1），当时问的是有没有办法减少两个复杂度