G家一道onsite题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

G家一道onsite题目

G家一道onsite题目# JobHunting - 待字闺中

e*82016-01-04 08:01

1 楼

题目是这道题的扩展
https://leetcode.com/problems/wiggle-sort/
1. 如果用单线程来解决，不难，网上有现成的解法。
2. 如果用多线程，可以加速，每个线程负责一段数据，最后把所有的都merge起来，也
不太难
3. 现在的问题是，如果确定到底需要多少个线程？假设内存无限大。
不知道最后一步要考察什么，求解答。。。

g*e2016-01-04 08:01

2 楼

这个不要merge吧。分成奇偶两个loop就没dependency了：
for(int i = 0; i < nums.length-1; i+=2)
if(nums[i] > nums[i+1])
//swap nums[i] and nums[i+1]

for(int i = 1; i < nums.length-1; i+=2)
if(nums[i] < nums[i+1])
//swap nums[i] and nums[i+1]