作者jason21716 (阿鸿)
看板Prob_Solve
标题[问题] 阵列中的比自己小的数字
时间Mon Oct 31 14:00:08 2016
各位好，小弟有一个演算法的问题想请教各位大大
有一个阵列，内有若N个不相同且随机排列的数字
如：2 8 6 1 9 10 13 0
我需要依照阵列顺序把排在自己之後而且比自己小的数字印出来
像这样：
2 1
2 0
8 6
8 1
8 0
6 1
6 0
9 0
10 0
13 0
我知道如果用回圈一个一个检查总是有结果的
但是演算法效率是O(n^2)
想请问各位有没有比O(n^2)更快的做法??
我想了很久，但都没有比较好的解法...
不好意思麻烦各位了
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 120.113.124.157
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1477893613.A.FC7.html
1F：推 ddavid: 极端来讲，我给你8 7 6 5 4 3 2 1，你光是印出答案就需要 10/31 14:35
2F：→ ddavid: O(n^2)，顶多系数可以给你最小化到1/2罢了 10/31 14:36
是呀...这一点让人很头疼...
那如果说今天在不要求顺序的状况下，有可能提升速度吗...
3F：推 ddavid: 直接做O(n log n) sort并保留原始顺序的link，期待印出步 10/31 14:50
4F：→ ddavid: 骤的次数期望值落在O(n log n)也许比较实在 10/31 14:52
5F：推 CaptainH: 考虑merge sort，在merge时加个一两行就行了 10/31 15:01
mergeSort吗...
可是mergeSort在merge时一次都只看左右两边各一个数字
如果今天左边的阵列数字全都比右边的大，那就会出问题了...
但这似乎也是个好主意...透过merge时将左右两边排好
我让左边的最大值开始扫描右边的最小值，
左>右就输出值对，左<右就换左遍次大的重来一遍
左边全部扫完之後就把两边merge起来
可是演算法效率...
mergeSort本身效率是O(nlogn)，但因为要扫描左右两边的大小
势必得再加上这个步骤的成本...
刚刚拿大师定理算了一下，最糟糕的状况(已经由大排到小)是O(n^2)
最好的状况(由小到大)是O(nlogn)，平均状况的话我在算算看
不过似乎是可行的做法....
....
不行，平均状况的结果算来算去应该也会是O(n^2)
还需要更快的方法才行
6F：→ pttworld: 类别二栏位index和value，排序後判断索引输出得解。 10/31 16:29
是像这样吗?
原阵列 2 8 6 1 9 10 13 0
索引 0 1 2 3 4 5 6 7
排序後
value 0 1 2 6 8 9 10 13
index 7 3 0 2 1 4 5 6
然後从13开始，往前找index比它还大的数字吗?
可是这样子的效率还是O(n^2)....
或许是我误解大大的意思了??
※ 编辑: jason21716 (120.113.124.157), 10/31/2016 17:40:14
7F：推 s89162504: mergesort怎会变成O(n^2) 10/31 19:52
8F：→ pttworld: 回原po，n个都要列出关系起算就n往上了。一楼说得很白。 10/31 20:05
9F：推 c225: 解的大小本来就Ω(n^2)了 所以merge sort复杂度应该是 11/01 00:20
10F：→ c225: O(nlogn + k) k是解大小~ 11/01 00:21
11F：推 DJWS: 比较快的方法应该是hashing/counting sort/位元操作之类的 11/01 10:38
12F：→ DJWS: 如果只能两两比较的话，那麽就是推文一楼说的那样子，接下来 11/01 10:39
13F：→ DJWS: 的方向会是随机算法/平滑分析之类的 11/01 10:39
14F：→ DJWS: 另外这题有个有趣的性质：当数值（连带索引值）重新排序之後 11/01 10:41
15F：→ DJWS: 问题变成找到後方的更大索引值，类似於原本问题，但是索引值 11/01 10:42
16F：→ DJWS: 的范围会是连续正整数，成为更简单一点的问题 11/01 10:43
17F：→ DJWS: 至於这性质有什麽用...我也不知道 XD 11/01 10:43
18F：→ rifiz: count inversion problem? 11/07 02:24
19F：推 Astar5566: 没错 只是要印出来 11/07 16:28
20F：推 HoloLens: 看起来超像逆序数对，merge nlogn不会漏判啊 11/28 23:23
21F：→ HoloLens: 为何要扫左右两边？ 11/28 23:24