这是一个创建于 4728 天前的主题，其中的信息可能已经有所发展或是发生改变。
请问有没有可能在O(nlogn)时间里同时完成排序和累积求和？
例如：
输入 {5, 2, 1, 3, 4}, 排序后是{1, 2, 3, 4, 5}, 再累积求和后是{1, 3, 6, 10, 15}
输出{1, 3, , 10, 15}.
例如：
输入 {5, 2, 1, 3, 4}, 排序后是{1, 2, 3, 4, 5}, 再累积求和后是{1, 3, 6, 10, 15}
输出{1, 3, , 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