一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 913|回复: 9
收起左侧

[算法题] 问一道G家面经里的题

[复制链接] |试试Instant~ |关注本帖
marthew777 发表于 2015-11-1 11:47:55 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Q: 给两个数组,第一个数组用0和1组成,1表示升序,0表示降序,根据这个数组将第二个数组重新排列,让第二个数组符合第一个数组所表示的规律.

这题看起来像wiggle sort的变形,但是不知道如何做到O(n), 我想出来的是先排序再扫一遍array进行排序,感觉不是很好。。求哪位大神指点一下优化的方法,谢谢啦!

补充内容 (2016-9-16 19:13):
假定条件:“被重新排列的数组中, 没有重复的数字”,或者“有重复数字但是相邻的相同数字既可看做升序,也可看做降序”。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · G|主题: 14, 订阅: 3
stellari 发表于 2015-11-2 08:51:55 | 显示全部楼层
marthew777 发表于 2015-11-2 02:43
大神提到generalize的思维方式的确让人眼前一亮,收益颇多,但是generalize之后,我觉得有一些变化导致时间 ...

我理解你的困惑,不过你完全不需要担心那6种情况,因为你只需像我2楼中说的,做这么一件事:

对于连续的Ai~Aj,把Bi~Bj+1排序即可。


这就可以处理那6种情况了。

就用你的例子来说明
A= {0000} {11} {00} {1} {000} ,  B = {10, 9, 8, 7, 6}, {5,4},{11,12},{3},{9,8,7}

A0~A3是0,那么把B0~B4按降序排列,得
B = {10, 9, 8, 7, 6}, ....
A4~A5是1,那么把B4~B6按升序排列,得
B = {10, 9, 8, 7, 4}, {5, 6}...
A6~A7是0,那么把B6~B7按降序排列,得
B = {10, 9, 8, 7, 4}, {5, 12}, {7, 6}...
...

看,每次对Ai~Aj排序时,都要用到“之前已经被排好的序列的最后一个数字”,即Bi。可以这么做的理由是:

如果Bi~Bj+1应该是升序,那么Bi~Bj+1之前的序列Bi'~Bj'+1一定是降序(此处i=j'+1)。对Bi~Bj+1排序完以后,此时的Bi应当是Bi~Bj+1中的最小;由于排序后的Bi一定不大于排序前的Bi(也就是Bj'+1),那么既然原来的Bj'+1是Bi'~Bj'+1中的最小值,那么对Bi~Bj+1排序过后的Bi(也就是Bj'+1)一定还是Bi'~Bj'+1中的最小值。

如果Bi~Bj+1是降序,也可同理得出类似结论。

换言之。这种排序方法绝对不会改变之前已经得到的升降序列。可以放心使用。

QED

评分

3

查看全部评分

回复 支持 3 反对 0

使用道具 举报

stellari 发表于 2015-11-1 17:47:49 | 显示全部楼层
本帖最后由 stellari 于 2015-11-1 17:49 编辑

这题可以看做wiggle sort的推广:wiggle sort中的第一个数组(以下记做A)中的连续1或0的最大长度为0,而此处连续1或0的长度可以任意。所以解法其实也可以由wiggle sort推广而来。

wiggle sort的解法是:如果第二个数组B中的Bi 和 Bi+1之间的关系不符合Ai,则交换Bi和Bi+1,使之符合。这一交换一定不会影响前面已排好的部分。

那么此处generalized wiggle sort的解法就是:在A中依次找出每一段连续的1(或0),每找出一段(比如范围是Ai ~ Aj),那么我们就对Bi~Bj+1部分排序,使其满足Ai~Aj这一递增或递减序列的要求。同理,这一排序也一定不会影响之前已排好的部分。

所以wiggle sort中的那个“交换”,其实本质上是“排序”。

PS:此处要假定一个条件:“数组中没有重复的数字”,或者“有重复数字但是相邻的相同数字既可看做升序,也可看做降序”。

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

stellari 发表于 2016-9-16 08:29:43 | 显示全部楼层
xh_pku 发表于 2016-9-13 08:29
我有一个疑问就是,如何能够保证这样做的时间复杂度是O(N)呢??在最坏情况下(全为1)不还是O(n * log n ...

没错, worst-case当然还是O(nlogn). 这题在理论上就不可能做到worst-case O(n). 否则,如果有方法能对此题实现worst-case O(n), 那么只要令A等于全0或全1,我们就能在O(n)时间内对任意的B降序或升序排列. 而这已经被证明是不可能的.

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| marthew777 发表于 2015-11-1 19:34:23 | 显示全部楼层
stellari 发表于 2015-11-1 17:47
这题可以看做wiggle sort的推广:wiggle sort中的第一个数组(以下记做A)中的连续1或0的最大长度为0,而此 ...

多谢大神指点,终于懂了。。 我被自己的蠢再次吓哭了,

大神,这是我的膝盖,请接收。。想给多点分,可惜3分是上限,
回复 支持 反对

使用道具 举报

 楼主| marthew777 发表于 2015-11-2 02:43:39 | 显示全部楼层
大神提到generalize的思维方式的确让人眼前一亮,收益颇多,但是generalize之后,我觉得有一些变化导致时间复杂度没有优化,worst case 比如A =  000000 , B = 1234567;反而变得更难实现了。

让我们再看一个例子, A= {0000} {11} {00} {1} {000} ,  B = {10, 9, 8, 7, 6}, {5,4},{11,12},{3},{9,8,7}
这里,{} = 分组情况, B里第一组永远是比A里第一组多一个元素,剩余的组元素个数相同,因为上一组的尾部元素会提供一个新的比较给当前组。
然后因为每一组里的元素是monotone的,所以可以看作是一个interval,比如B1 = [6,10],这个接下来分析的时候有用。

那第一步,我们给第一组和第二组里的元素按照0或者1,分别sort, 处理得到interval的范围;
第二步swap,这里generalize 之后的swap和以前不太一样了,当需要swap的时候,不是把两个组看做整体直接swap两个组的位置,
而是要从前后两个interval里找到合理的元素在不破坏其他的大小顺利的前提下进行swap,这里的case有这么6种。。

B1 ([6,10])    --   B2([4,5])

B1 被包含或者包含 B2 (2种)
B1 于 B2 相交 (2种)
B1 于 B2 不想交 (2种)

有的情况会比较恶心,比如,B1 -B2 需要升序,但是B2与B1不想交而且都小,这个时候需要把B2里的元素全部swap到B1里。。

请教大神我是不是哪里做错了或者如何改进。。多谢啦!
回复 支持 反对

使用道具 举报

 楼主| marthew777 发表于 2015-11-2 10:03:29 | 显示全部楼层
stellari 发表于 2015-11-2 08:51
我理解你的困惑,不过你完全不需要担心那6种情况,因为你只需像我2楼中说的,做这么一件事:

对于连续 ...

太好啦!终于解决了这个问题!最后代码好简短。。多谢大神的耐心指点!太攒了
回复 支持 反对

使用道具 举报

mmliu 发表于 2015-11-17 13:56:49 | 显示全部楼层
本帖最后由 mmliu 于 2015-11-17 14:13 编辑
stellari 发表于 2015-11-2 08:51
我理解你的困惑,不过你完全不需要担心那6种情况,因为你只需像我2楼中说的,做这么一件事:

对于连续 ...

很赞的思路,学习啦 这样也算彻底想明白wiggle sort了

----发现地里居然可以编辑了 de 分割线----


不过话说回来,题意应该再明确下,比如[0 0 1]表示的是 第0 到 第2个 元素为递减,第2到第3个元素为递增。


回复 支持 反对

使用道具 举报

xh_pku 发表于 2016-9-13 08:29:41 | 显示全部楼层
stellari 发表于 2015-11-2 08:51
我理解你的困惑,不过你完全不需要担心那6种情况,因为你只需像我2楼中说的,做这么一件事:

对于连续 ...

我有一个疑问就是,如何能够保证这样做的时间复杂度是O(N)呢??在最坏情况下(全为1)不还是O(n * log n)吗??
回复 支持 反对

使用道具 举报

zhan8803705 发表于 2016-9-14 08:48:37 | 显示全部楼层
同问,这样worst case不是O(nlogn)?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 12:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表