这是一个创建于 4727 天前的主题，其中的信息可能已经有所发展或是发生改变。
请问有没有可能在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}.
10 条回复 • 1970-01-01 08:00:00 +08:00
 |
1
013231 2013 年 1 月 31 日  1
O(nlogn) + O(n)還是O(nlogn).
|
 |
2
uoryon 2013 年 1 月 31 日 1
可是尝试计数排序...但是对数据有些许限制
|
 |
4
notonlysuccess 2013 年 1 月 31 日 1
|
 |
5
laskuma 2013 年 1 月 31 日 1
@notonlysuccess 1楼意思是O(nlogn) + O(n)(依然)还是O(nlogn)
|
 |
6
test123 OP 多谢回复，数量级上去了之后nlogn跟nlogn+n差距也不小呀。
|
Select Language