时间复杂度最低的方法是,修改归并排序(Merge Sort),在排序同时对逆序对计数。时间复杂度为 \(O(n\log{n})\)。
代码:
1 | class Solution { |
注意:data[i] <= data[j]
这里不能写成<
,因为在两个数相同的情况下,先选取左边的才能让总和尽可能小。比如 [1,2,1,2,1]
的逆序和是3,而不是7。
Ref.
- 《剑指Offer》何海涛
时间复杂度最低的方法是,修改归并排序(Merge Sort),在排序同时对逆序对计数。时间复杂度为 \(O(n\log{n})\)。
代码:
1 | class Solution { |
注意:data[i] <= data[j]
这里不能写成<
,因为在两个数相同的情况下,先选取左边的才能让总和尽可能小。比如 [1,2,1,2,1]
的逆序和是3,而不是7。
Ref.