请问有没有可能在O(nlogn)时间里同时完成排序和累积求和？
例如：
输入 {5, 2, 1, 3, 4}, 排序后是{1, 2, 3, 4, 5}, 再累积求和后是{1, 3, 6, 10, 15}
输出{1, 3, 6, 10, 15}.
例如：
输入 {5, 2, 1, 3, 4}, 排序后是{1, 2, 3, 4, 5}, 再累积求和后是{1, 3, 6, 10, 15}
输出{1, 3, 6, 10, 15}.
This topic created in 4850 days ago, the information mentioned may be changed or developed.
10 replies • 1970-01-01 08:00:00 +08:00
 |
1
013231 Jan 31, 2013  1
O(nlogn) + O(n)還是O(nlogn).
|
 |
2
uoryon Jan 31, 2013 1
可是尝试计数排序...但是对数据有些许限制
|
 |
4
notonlysuccess Jan 31, 2013 1
|
 |
5
laskuma Jan 31, 2013 1
@notonlysuccess 1楼意思是O(nlogn) + O(n)(依然)还是O(nlogn)
|
 |
6
test123 OP 多谢回复，数量级上去了之后nlogn跟nlogn+n差距也不小呀。
|
Select Language