Google Japan 店面

shuyangsheng 发表于 2016-7-27 04:30
直接用QuickSelect找中位数最差情况应该不是O(n)吧。每次Select是O(n)，但是找到的pivot不一定是中位数， ...

average 是 O(n)  worst case是 O(n^2)

同乡顶一下！

mkcing 发表于 2016-7-27 05:04
average 是 O(n)  worst case是 O(n^2)

worst case 应该是O(nlogn)吧，这不是完整的quick sort。我不是很确定。。。

其实这题greedy就可以了：

1.     def wiggleSort(self, nums):
   
2.         # Write your code here
   
3.         for i in range(1,len(nums)):
   
4.             if (i%2==0 and nums[i] > nums[i-1]) or (i%2==1 and nums[i] < nums[i-1]):
   
5.                 nums[i],nums[i-1] = nums[i-1],nums[i]

复制代码

举个例子 a=[3,1,4]，那么要求就是[a0 a1] 上升，[a1,a2] 下降。
第一步 [a0 a1] 交换，得到[1,3,4]，这时候[a0 a1] 满足了上升条件。
第二步 [a1 a2]=[3,4] 要求下降，所以要交换成[1,4,3]。
我们知道 3 是大于 1 的，而 4 > 3,  所以 4 必然大于 3，所以 4 > 1 必然成立，也就是说后面的交换并不影响前面已经wiggle排好的序列。

找中位数的做法我写了半天也不太对，可能智商有限，数列长度是奇数的时候中间那个元素怎么处理有点捉急。。。

shuyangsheng 发表于 2016-7-27 05:59
worst case 应该是O(nlogn)吧，这不是完整的quick sort。我不是很确定。。。

其实这题greedy就可以了 ...

这道题用 greedy 是不对的，
如果题目是 a1 >= a2 <= a3 >= a4 <= a5

那么用 greedy 是对的。

比如， 5,5,5, 1,2,3,4,6,7,8,9,  你看看能不能用greedy?

hello , I am sorry that i cannot type Chinese now.
Did you answer only this question? did the recruiter ask any other questions?
Also , is this  interview for intern or full-time?