一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 976|回复: 8
收起左侧

[二分/排序/搜索] 求助一道排序算法题,脑阔疼!

[复制链接] |试试Instant~ |刷题, 二分/排序/搜索
我的人缘0

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
一个大于等于3的数组 然后是乱序的 其中的任意三个数字(不一定连续) a,b,c 可以换序变成b,c,a, 可以换很多次,那这个数组里的数可以不可以通过这个规律把它变成升序排列呢?

上一篇:leetcode会员出售或share
下一篇:出leetcode账号英文版到8月中旬
我的人缘0
magicsets 2020-2-22 19:40:10 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   99% (1046)
 
 
0% (8)    👎
本帖最后由 magicsets 于 2020-2-22 19:41 编辑

楼上所说的逆序对的判定方法是正确的,但如果要解释为什么的话需要一些基本的群论知识,这里稍微展开一下..

为了简化讨论我们假定数组里没有重复元素(而且有重复元素也没法做到题目所要求的“升序排列”)

1.

三元素轮换 "a,b,c -> b,c,a"(并且其他元素位置不变)是置换(permutation)的特例,叫做3-cycle,可以记作 (a, b, c)

比如说如果数组长度为4的话,记数组元素的位置为1,2,3,4,那么有12种3-cycle:

(1, 2, 3): 1号元素换到2号,2号换到3号,3号换到1号,4号不动
(1, 3, 2): 1号元素换到3号,3号换到2号,2号换到1号,4号不动
(1, 2, 4): 1号元素换到2号,2号换到4号,3号不动,4号换到1号
...

2.

先不考虑3-cycle,考虑一个长度为 n 的数组,其有 n! 种重排方式

那么所有重排方式构成一个拥有 n! 个元素的置换群,称为对称群(symmetric group),记作 Sn

3.

定理:对于长度为n的数组,考虑所有可能的三元素轮换的组合,所得到的重排的集合一定是n阶 “交错群”(alternating group),记作An,其是Sn中所有偶置换构成的一个子集(准确来说是个正规子群),元素数量一定为 n! / 2

这里涉及的一个重要概念就是置换的奇偶性,参考:
https://www.cnblogs.com/1036464679hxl/p/7845814.html

相关证明可以参考这个notes里面的Lemma 3.1:
https://kconrad.math.uconn.edu/blurbs/grouptheory/genset.pdf
其实notes里面还有更强的一个结论(Theorem 3.4):每次只需要轮换相邻的三个元素,就可以得到An中的任意重排

4.

现在,我们考虑从数组原来的顺序到升序的置换 P,原问题的就等价于问 P 是否在 An 中

举个例子,考虑长度为4的数组 [40 30 10 20],那么目标的升序数组就是 [10, 20, 30, 40]

那么对应的置换 P 的轮换表示就是 (1,4,2,3)
也就是1号位置的40要换到4号位置去,2号位置的30要换到3号位置,3号位置的10要换到1号位置,4号位置的20要换到2号位置

然而 A4 的12个置换中并不包含 (1, 4, 2, 3):
https://groupprops.subwiki.org/wiki/A4_in_S4

所以 [40 30 10 20] 并不能通过三元素轮换的方法转换到 [10 20 30 40]

5.

现在是最后一步了,给定一个长度为 n 的数组,如何判定是否可以得到升序?

两种方法,都是nlog(n)时间:

(1) 将原数组排序 -> 求置换 P -> 判定 P 是否是偶置换

排序O(n log(n)),求置换及判定 O(n),参考:https://stackoverflow.com/questi ... ty-of-a-permutation

(2) 将原数组归并排序 -> 过程中数逆序对数量 -> 判定奇偶性

也是O(n log(n))。至于为什么逆序对数量的奇偶性与置换 P 的奇偶性一致,上面写的第3点的那个cnblogs链接中有证明


补充内容 (2020-2-23 05:30):
第1部分中“12种3-cycle” -> “8种3-cycle”

评分

参与人数 4大米 +24 收起 理由
anhpp + 2 给你点个赞!
苏糖糖糖 + 1 给你点个赞!
14417335 + 20
Shilcare + 1 赞一个!

查看全部评分

回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (21)
 
 
0% (0)    👎
当然不可以了,(3,2,1),你怎么转都不是升序啊

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| 苏糖糖糖 2020-2-22 00:14:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
凤歌打狐狸 发表于 2020-2-22 00:07
当然不可以了,(3,2,1),你怎么转都不是升序啊

对 你说的这个case是不可以的 但是问题是给定一个任意的要判断一下是否可以~
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (2944)
 
 
11% (387)    👎
我明白了。你这个算法其实是看是否数列是 旋转过的

补充内容 (2020-2-21 08:26):
是可以的,首先找到数列里最小的数,以它为起点 扫一遍,o(n) 时间搞定。

for (i = n - 1; i < n + leng; i++) {
  i = i % n;

}
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (21)
 
 
0% (0)    👎
苏糖糖糖 发表于 2020/02/22 00:14:25
对 你说的这个case是不可以的 但是问题是给定一个任意的要判断一下是否可以~
那这个也很简单,你把所有乱序对数加起来,如果是偶数就可以,奇数就不可以,最粗暴的count就是O(n^2)了,也可以用排序来做那就是O(n log n),至于能不能O(n)你可以想一想🤔️

评分

参与人数 1大米 +1 收起 理由
苏糖糖糖 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (21)
 
 
0% (0)    👎
magicsets 发表于 2020/02/22 19:40:10
楼上所说的逆序对的判定方法是正确的,但如果要解释为什么的话需要一些基本的群论知识,这里稍微展开一下..

为了简化讨...
哈哈哈,我就说了个解答,你就把证明搬来了,我觉得这里大部分人不太在意背后的数学原理,其实数学才是算法里的黑魔法👌
回复

使用道具 举报

我的人缘0
 楼主| 苏糖糖糖 2020-2-23 01:52:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
magicsets 发表于 2020-2-22 19:40
楼上所说的逆序对的判定方法是正确的,但如果要解释为什么的话需要一些基本的群论知识,这里稍微展开一下.. ...

您真是太6了!!!让我想起了好几年前学的抽象代数hhh
回复

使用道具 举报

我的人缘0
huntersjm 2020-2-23 15:29:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (90)
 
 
0% (0)    👎
你得每次变化都是 逆序数为偶数,所以如果你原先的数据的逆序是奇数,就不可能通过这种方法排序。同理,如果逆序数为2,可以通过构造的方法,保持逆序数一直减少,就能最终变成0。这里存在两种可能,一种是 3,1,2,这种可以通过两次旋转得到1,2,3,是的逆序数减少2,另一种是,3,2,1 可以通过一次旋转得到1,3,2也能减少逆序数2.总之,只要存在乱序,就能保持逆序数一直减少,直到 逆序数%2。由此可能,充分必要条件是逆序数为偶数。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-4-7 08:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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