jz51.数组中的逆序对

题目描述

题解

暴力方法(超时)

就是使用一个双循环结构计算出全部的逆序对, 结果超时:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int reversePairs(int[] nums) {
if (nums.length == 0 || nums.length == 1) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 0;
for (int i = 1; i < nums.length; i++) {
int n = 0;
for (int j = 0; j < i; j++) {
if (nums[i] < nums[j]) {
n++;
}
dp[i] = dp[i - 1] + n;
}
}
return dp[nums.length - 1];
}
}

归并排序

如果编写递归函数,每一次都一分为二拆分数组的子区间,然后在方法栈弹出的时候,一步一步合并两个有序数组,最后完成排序工作。

而计算逆序数就发生在排序的过程中,利用了「排序」以后数组的有序性。

  • 关键在于合并两个有序数组的步骤, 利用数组的部分有序性, 一下子计算出一个数之前或者之后元素的逆序的个数
  • <分>的时候什么也不做, <合>的时候计算逆序对的个数
  • 排序工作是必要的, 正是因为排序才能在下一轮利用顺序关系加快逆序数的计算,也能避免重复计算

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class jz51 {
public int reversePairs(int[] nums) {

int len = nums.length;

if (len < 2) {
return 0;
}

return merge(nums, 0, len - 1);
}

private int merge(int[] nums, int left, int right) {

if (left >= right) {
return 0;
}

int mid = left + (right - left) / 2;

int leftPartition = merge(nums, left, mid);
int rightPartition = merge(nums, mid + 1, right);

if (nums[mid] <= nums[mid + 1]) {
return leftPartition + rightPartition;
}

int cross = mergeTwo(nums, left, mid, right);
return leftPartition + cross + rightPartition;
}

private int mergeTwo(int[] nums, int left, int mid, int right) {
int length = right - left + 1;
int[] temp = new int[length];

if (length >= 0) {
System.arraycopy(nums, left, temp, 0, length);
}

int count = 0;
int l = 0;
int mid_temp = mid - left;
int r = mid - left + 1;

for (int i = 0; i < length; i++) {
if (l > mid - left) {
nums[left + i] = temp[r];
r++;
} else if (r > length - 1) {
nums[left + i] = temp[l];
l++;
} else if (temp[l] <= temp[r]) {
nums[left + i] = temp[l];
l++;
} else if (temp[r] < temp[l]) {
nums[left + i] = temp[r];
r++;
count += mid - left - l + 1;
}
}

return count;
}
}
-------------本文结束感谢您的阅读-------------
可以请我喝杯奶茶吗