剑指offer51 数组中的逆序对【分治、归并】

剑指 Offer 51. 数组中的逆序对

题目描述

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例 1:

1
2
输入: [7,5,6,4]
输出: 5

限制:

1
0 <= 数组长度 <= 50000

解题思路

方法一:归并排序

利用分治算法思想,归并排序,在归并的过程中计算逆序对的大小;

具体思路讲解可前往leetcode网站上观看视频讲解,了解已在资料中给出。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public int reversePairs(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
int temp[] = new int[nums.length];
return mergeSort(nums, 0, nums.length - 1, temp);
}

private int mergeSort(int[] nums, int left, int right, int[] temp) {
if (left == right) {
return 0;
}
int mid = left + (right - left) / 2;
int leftPairs = mergeSort(nums, left, mid, temp);
int rightPairs = mergeSort(nums, mid + 1, right, temp);

if (nums[mid] <= nums[mid + 1]) {
return leftPairs + rightPairs;
}

int mergePairs = merge(nums, left, mid, right, temp);
return leftPairs + rightPairs + mergePairs;
}

private int merge(int[] nums, int left, int mid, int right, int[] temp) {
int i = left, j = mid + 1;
int count = 0;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {
temp[k] = nums[j++];
} else if (j == right + 1) {
temp[k] = nums[i++];
} else if (nums[i] <= nums[j]) {
temp[k] = nums[i++];
} else {
temp[k] = nums[j++];
count += mid - i + 1;
}
}
for (int k = left; k <= right; k++) {
nums[k] = temp[k];
}
return count;
}
}

复杂度分析

时间复杂度:O(n log n )

空间复杂度:O(1)

方法二:暴力法

两重循环遍历判断是否存在逆序对

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {

public int reversePairs(int[] nums) {
int count = 0;
int len = nums.length;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] > nums[j]) {
count++;
}
}
}
return count;
}
}

复杂度分析

时间复杂度:O($n^2$ )

空间复杂度:O(1)

资料

剑指offer51 数组中的逆序对【分治、归并】

http://example.com/2021/05/29/剑指offer51-数组中的逆序对/

Author

John Doe

Posted on

2021-05-29

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.