G家四月onsite

zestypanda87 发表于 2018-4-13 04:05
第四题没说只有一个重复元素啊 也没说只重复一次啊

啊，1-n个元素，数组长度为n+1，我的理解是只有一个重复元素，也许不是吧。

idatascience 发表于 2018-4-13 06:11
啊，1-n个元素，数组长度为n+1，我的理解是只有一个重复元素，也许不是吧。

因为题目中说 “任意一个”，我感觉可能不止一个重复元素 也不止一次
楼主给了四种解法 应该比较直接易懂 第三种解法是binary search

zestypanda87 发表于 2018-4-13 06:52
因为题目中说 “任意一个”，我感觉可能不止一个重复元素 也不止一次
楼主给了四种解法 应该比较直接易 ...

确实是有可能不止一个重复元素。第三种确实是binary search。

楼主想问下第二轮是不是有点类似利口斯舞林呢？
这个树是BST吗？

Ramily 发表于 2018-4-13 21:03
楼主想问下第二轮是不是有点类似利口斯舞林呢？
这个树是BST吗？

不是bst，字数字数

zestypanda87 发表于 2018-4-13 06:52
因为题目中说 “任意一个”，我感觉可能不止一个重复元素 也不止一次
楼主给了四种解法 应该比较直接易 ...

请问一下 第四题 nlogn解法 原数组不是sort的 怎么binary search啊？

第四轮，还有一种类似链表找环的做法，O(n)时间复杂度，O(1)空间复杂度，而且不改变原数组
https://segmentfault.com/a/1190000003817671

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

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

qqiq 发表于 2018-4-14 21:29
binary search on value, not index. 每次value range 减半，check （O(n)) if 在这个范围里面的数超过了 ...

太机智了~ thanks