Skip to content

Commit 411f366

Browse files
coderbruiscoderbruis
committed
[A] 添加leetcode题解：逆序对
1 parent 64c6917 commit 411f366

1 file changed

Lines changed: 150 additions & 0 deletions

File tree

‎src/main/java/com/bruis/algorithminjava/algorithm/leetcode/ReversePairs.java‎

Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
package com.bruis.algorithminjava.algorithm.leetcode;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* 逆序对
7+
* <p>
8+
* url： https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
9+
*
10+
* @author LuoHaiYang
11+
*/
12+
public class ReversePairs {
13+
14+
/* ================================ 解法一 ================================*/
15+
16+
/**
17+
* 暴力解法O(n^2)，超时
18+
*
19+
* @param nums
20+
* @return
21+
*/
22+
public int reversePairs2(int[] nums) {
23+
int n = nums.length;
24+
if (n < 2) {
25+
return 0;
26+
}
27+
int reverseNum = 0;
28+
for (int i = 0; i < n; i++) {
29+
for (int j = i + 1; j < n; j++) {
30+
if (nums[i] > nums[j]) {
31+
reverseNum++;
32+
}
33+
}
34+
}
35+
return reverseNum;
36+
}
37+
38+
/* ================================ 解法二 ================================*/
39+
40+
/**
41+
* 使用自顶向下的归并排序算法计算逆序对，用来额外的空间。
42+
*
43+
* @param nums
44+
* @return
45+
*/
46+
public int reversePairs(int[] nums) {
47+
int n = nums.length;
48+
if (n < 2) {
49+
return 0;
50+
}
51+
return getReversePairs(nums);
52+
}
53+
54+
private int getReversePairs(int[] nums) {
55+
int n = nums.length;
56+
return getReversePairs(nums, 0, n - 1);
57+
}
58+
59+
private int getReversePairs(int[] nums, int left, int right) {
60+
if (left >= right) {
61+
return 0;
62+
}
63+
int result = 0;
64+
int mid = (left + right) / 2;
65+
result += getReversePairs(nums, left, mid) + getReversePairs(nums, mid + 1, right) + reversePairs(nums, left, mid, right);
66+
return result;
67+
}
68+
69+
private int reversePairs(int[] nums, int left, int mid, int right) {
70+
int[] aux = Arrays.copyOfRange(nums, left, right + 1);
71+
int i = left, j = mid + 1;
72+
73+
int res = 0;
74+
75+
for (int k = left; k <= right; k++) {
76+
if (i > mid) {
77+
nums[k] = aux[j - left];
78+
j++;
79+
} else if (j > right) {
80+
nums[k] = aux[i - left];
81+
i++;
82+
} else if (aux[i - left] <= aux[j - left]) {
83+
nums[k] = aux[i - left];
84+
i++;
85+
} else {
86+
nums[k] = aux[j - left];
87+
j++;
88+
res += (mid - i) + 1;
89+
}
90+
}
91+
return res;
92+
}
93+
94+
/* ================================ 题解三（优化） ================================*/
95+
96+
/**
97+
* @param nums
98+
* @return
99+
*/
100+
public int reversePairs3(int[] nums) {
101+
if (nums == null || nums.length < 2)
102+
return 0;
103+
int[] temp = new int[nums.length];
104+
System.arraycopy(nums, 0, temp, 0, nums.length);
105+
106+
int count = mergeCount(nums, temp, 0, nums.length - 1);
107+
return count;
108+
}
109+
110+
private int mergeCount(int[] nums, int[] temp, int start, int end) {
111+
if (start >= end) {
112+
return 0;
113+
}
114+
115+
int mid = (start + end) >> 1;
116+
int left = mergeCount(temp, nums, start, mid);
117+
int right = mergeCount(temp, nums, mid + 1, end);
118+
int count = 0;
119+
120+
//merge()
121+
int i = mid;//遍历左区域指针
122+
int j = end;//遍历右区域指针
123+
124+
int k = end;//临时区域指针
125+
while (i >= start && j >= mid + 1) {
126+
if (nums[i] > nums[j]) {
127+
count += j - mid;
128+
temp[k--] = nums[i--];
129+
} else {
130+
temp[k--] = nums[j--];
131+
}
132+
}
133+
//如果还有剩下没遍历的
134+
while (i >= start)
135+
temp[k--] = nums[i--];
136+
while (j >= mid + 1)
137+
temp[k--] = nums[j--];
138+
139+
return count + left + right;
140+
}
141+
142+
public static void main(String[] args) {
143+
ReversePairs reversePairs = new ReversePairs();
144+
int[] nums = {7, 5, 6, 4};
145+
//int[] nums = {1,3,2,3,1};
146+
System.out.println(reversePairs.reversePairs3(nums));
147+
}
148+
149+
150+
}

0 commit comments

Comments
 (0)