剑指offer51 数组中的逆序对【分治、归并】
剑指 Offer 51. 数组中的逆序对
题目描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
示例 1:
1 | 输入: [7,5,6,4] |
限制:
1 | 0 <= 数组长度 <= 50000 |
解题思路
方法一:归并排序
利用分治算法思想,归并排序,在归并的过程中计算逆序对的大小;
具体思路讲解可前往leetcode网站上观看视频讲解,了解已在资料中给出。
代码实现
1 | class Solution { |
复杂度分析
时间复杂度:O(n log n )
空间复杂度:O(1)
方法二:暴力法
两重循环遍历判断是否存在逆序对
代码实现
1 | public class Solution { |
复杂度分析
时间复杂度:O($n^2$ )
空间复杂度:O(1)
资料
剑指offer51 数组中的逆序对【分治、归并】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.