各位好，小弟有一个算法的问题想请教各位大大
有一个阵列，内有若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)更快的做法??
我想了很久，但都没有比较好的解法...
不好意思麻烦各位了
作者:
ddavid (谎言接线生)
2016-10-31 14:35:00极端来讲，我给你8 7 6 5 4 3 2 1，你光是印出答案就需要O(n^2)，顶多系数可以给你最小化到1/2罢了直接做O(n log n) sort并保留原始顺序的link，期待印出步骤的次数期望值落在O(n log n)也许比较实在
作者:
CaptainH (Cannon)
2016-10-31 15:01:00考虑merge sort，在merge时加个一两行就行了
作者:
pttworld (批踢踢世界)
2016-10-31 16:29:00类别二字段index和value，排序后判断索引输出得解。
作者:
pttworld (批踢踢世界)
2016-10-31 20:05:00回原po，n个都要列出关系起算就n往上了。一楼说得很白。
作者: c225 (嘟嘟噜~~~) 2016-11-01 00:20:00
解的大小本来就Ω(n^2)了 所以merge sort复杂度应该是O(nlogn + k) k是解大小~
作者:
DJWS (...)
2016-11-01 10:38:00比较快的方法应该是hashing/counting sort/位元操作之类的如果只能两两比较的话，那么就是推文一楼说的那样子，接下来的方向会是随机算法/平滑分析之类的另外这题有个有趣的性质：当数值（连带索引值）重新排序之后问题变成找到后方的更大索引值，类似于原本问题，但是索引值的范围会是连续正整数，成为更简单一点的问题至于这性质有什么用...我也不知道 XD
作者:
rifiz (萨哈拉雅)
2016-11-07 02:24:00count inversion problem?
作者:
HoloLens (GoogleGlass没了ww)
2016-11-28 23:23:00看起来超像逆序数对，merge nlogn不会漏判啊为何要扫左右两边？