问一道G家面经里的题

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

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

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

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

这题可以看做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：此处要假定一个条件：“数组中没有重复的数字”，或者“有重复数字但是相邻的相同数字既可看做升序，也可看做降序”。

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降序或升序排列. 而这已经被证明是不可能的.

stellari 发表于 2015-11-1 17:47
这题可以看做wiggle sort的推广：wiggle sort中的第一个数组（以下记做A）中的连续1或0的最大长度为0，而此 ...

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

大神，这是我的膝盖，请接收。。想给多点分，可惜3分是上限，

大神提到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里。。

请教大神我是不是哪里做错了或者如何改进。。多谢啦！

stellari 发表于 2015-11-2 08:51
我理解你的困惑，不过你完全不需要担心那6种情况，因为你只需像我2楼中说的，做这么一件事：

对于连续 ...

太好啦！终于解决了这个问题！最后代码好简短。。多谢大神的耐心指点！太攒了

stellari 发表于 2015-11-2 08:51
我理解你的困惑，不过你完全不需要担心那6种情况，因为你只需像我2楼中说的，做这么一件事：

对于连续 ...

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

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


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

stellari 发表于 2015-11-2 08:51
我理解你的困惑，不过你完全不需要担心那6种情况，因为你只需像我2楼中说的，做这么一件事：

对于连续 ...

我有一个疑问就是，如何能够保证这样做的时间复杂度是O(N)呢？？在最坏情况下（全为1）不还是O(n * log n)吗？？

同问，这样worst case不是O(nlogn)？