4/12 Google Onsite (MTV) Cloud组

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

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

第五题应该可以用bucket sort那种思路来做，因为已经告诉了是从1到n的自然数，那么就把数列里的数都放回到 i-1 位，最后再从头扫一遍哪个位置不匹配，就是那个数不对了
leetcode里的那个missing number应该是类似的吧

第五题尝试写了一下：

1. class Solution(object):
   
2.     def findDuplicate(self,nums):
   
3.         if len(nums)<2:
   
4.             return None
   
5.         if len(nums) == 2:
   
6.             return nums[0]
   
7.         duplicate = None
   
8.         for i in xrange(len(nums)):
   
9.             while i+1!= nums[i]:
   
10.                 ind = nums[i]-1
    
11.                 temp = nums[i]
    
12.                 if duplicate and duplicate == temp:
    
13.                     return temp
    
14.                 nums[i] = nums[ind]
    
15.                 nums[ind] = temp
    
16.                 duplicate = temp

复制代码

肯定是被三哥黑了。很正常，我也这样。

第三轮似乎是老题啊 好像只能从末尾往前看

tinyrookie 发表于 2016-5-1 14:52
你补充的代码，里面while(nums != i+1)是什么意思？nums不是数组名吗

楼下说对，一部分code被吃掉了

zacharyzhy 发表于 2016-5-2 14:35
第五题应该可以用bucket sort那种思路来做，因为已经告诉了是从1到n的自然数，那么就把数列里的数都放回到  ...

bucket sort需要多余的空间，直接归位就可以了

Effiel 发表于 2016-5-3 12:41
bucket sort需要多余的空间，直接归位就可以了

恩，我说的可能有点不明白，思路是和bucketsort一样，不过就是你说的归位，用现有的array就可以了

第三轮是不是纯找规律啊 需要code么？
感觉就是k前面四位是1的话那n-1个数就在k-8位，
要是k前面四位是0的话就数0前面每四位连续几个1，奇数个那n-1个数在k-8位开始，偶数个在k-4位开始。

第五题能不能前后数组分别异或一下 然后差 / 2 就是结果?