MS on campus USC

在地里发的第一个帖子。面试30分钟，大概一半的时间都在讲背景经历。
题目
给一个sorted array。 所有it

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

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

;

给了hint才做出来，也来求一波人品。

z001242001 发表于 2017-10-23 02:49
可以問一下binary search的做法明確是怎麼樣呢？
謝謝~

因为总长度假设是2n+1，2n代表有n对数字。 当你用binary search的时候第一次取的是第n+1位，然后你用n+1位先和n位比，如果a[n] = a[n+1]就说明这n+1个数当中有一个奇数，否则就在另一边。
基本上就是2分的时候如果mid和前一个数相等那么出现一次的就在左边；和后一个数相等那么出现一次的数就在右边。这里二分的时候是包含这个mid的，这样每次子数组都是奇数位然后左右两边元素个数都相等。

如果nums = {1,1,2}的话 用这种方法“基本上就是2分的时候如果mid和前一个数相等那么出现一次的就在左边；和后一个数相等那么出现一次的数就在右边。这里二分的时候是包含这个mid的，这样每次子数组都是奇数位然后左右两边元素个数都相等。”  
感觉会有问题 nums[mid] == nums[mid - 1] = 1但是出现一次的数在右边

avenxyc 发表于 2017-10-23 06:34
因为总长度假设是2n+1，2n代表有n对数字。 当你用binary search的时候第一次取的是第n+1位，然后你用n+1 ...

十分感謝！！！  原來是這樣的思路  感覺leetcode有看過類似的題，但一時想不起來

可以問一下binary search的做法明確是怎麼樣呢？
謝謝~

感觉这道题是要找规律啊~~lc新题~~楼主好样的

avenxyc 发表于 2017-10-23 06:34
因为总长度假设是2n+1，2n代表有n对数字。 当你用binary search的时候第一次取的是第n+1位，然后你用n+1 ...

需要判断一下n是奇数还是偶数吧

YUANSHAO 发表于 2017-10-24 04:00
需要判断一下n是奇数还是偶数吧

说了所有的都是两个数只有一个只出现一次，所以N肯定是奇数

YUANSHAO 发表于 2017-10-24 03:55
如果nums = {1,1,2}的话 用这种方法“基本上就是2分的时候如果mid和前一个数相等那么出现一次的就在左边； ...

谢谢提醒，忘记说明迭代的最终情况了

请问一下lz是在10.11号usc上的career fair上投的简历吗？ 是当场面试还是过了几天之后电面啊？