Skip to content

Commit bad1546

Browse files
yanglbmeyanglbme
committed
feat: add python and java solutions to lcof question
添加《剑指 Offer》题解：面试题51. 数组中的逆序对
1 parent 625582c commit bad1546

4 files changed

Lines changed: 215 additions & 0 deletions

File tree

‎.github/workflows/sync.yml‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
name: Sync
2+
3+
on:
4+
push:
5+
branches: [ master ]
6+
7+
jobs:
8+
build:
9+
runs-on: ubuntu-latest
10+
steps:
11+
- name: Sync to Gitee
12+
uses: wearerequired/git-mirror-action@master
13+
env:
14+
SSH_PRIVATE_KEY: ${{ secrets.GITEE_RSA_PRIVATE_KEY }}
15+
with:
16+
source-repo: "[email protected]:doocs/leetcode.git"
17+
destination-repo: "[email protected]:Doocs/leetcode.git"

‎lcof/面试题51. 数组中的逆序对/README.md‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
# [面试题51. 数组中的逆序对](https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)
2+
3+
## 题目描述
4+
<!-- 这里写题目描述 -->
5+
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
6+
7+
**示例 1:**
8+
9+
```
10+
输入: [7,5,6,4]
11+
输出: 5
12+
```
13+
14+
**限制：**
15+
16+
- `0 <= 数组长度 <= 50000`
17+
18+
## 解法
19+
<!-- 这里可写通用的实现逻辑 -->
20+
在归并中统计逆序对。
21+
22+
### Python3
23+
<!-- 这里可写当前语言的特殊实现逻辑 -->
24+
25+
```python
26+
class Solution:
27+
def reversePairs(self, nums: List[int]) -> int:
28+
self.res = 0
29+
30+
def merge(part1, part2, nums):
31+
len1, len2 = len(part1) - 1, len(part2) - 1
32+
t = len(nums) - 1
33+
while len1 >= 0 and len2 >= 0:
34+
if part1[len1] > part2[len2]:
35+
self.res += (len2 + 1)
36+
nums[t] = part1[len1]
37+
len1 -= 1
38+
else:
39+
nums[t] = part2[len2]
40+
len2 -= 1
41+
t -= 1
42+
while len1 >= 0:
43+
nums[t] = part1[len1]
44+
t -= 1
45+
len1 -= 1
46+
while len2 >= 0:
47+
nums[t] = part2[len2]
48+
t -= 1
49+
len2 -= 1
50+
51+
def merge_sort(nums):
52+
if len(nums) < 2:
53+
return
54+
mid = len(nums) // 2
55+
s1, s2 = nums[:mid], nums[mid:]
56+
merge_sort(s1)
57+
merge_sort(s2)
58+
merge(s1, s2, nums)
59+
60+
merge_sort(nums)
61+
return self.res
62+
63+
```
64+
65+
### Java
66+
<!-- 这里可写当前语言的特殊实现逻辑 -->
67+
68+
```java
69+
class Solution {
70+
private int res = 0;
71+
public int reversePairs(int[] nums) {
72+
int n = nums.length;
73+
if (n < 2) {
74+
return 0;
75+
}
76+
mergeSort(nums, 0, n - 1);
77+
return res;
78+
}
79+
80+
private void mergeSort(int[] nums, int s, int e) {
81+
if (s == e) {
82+
return;
83+
}
84+
int mid = s + ((e - s) >> 1);
85+
mergeSort(nums, s, mid);
86+
mergeSort(nums, mid + 1, e);
87+
merge(nums, s, mid, e);
88+
}
89+
90+
private void merge(int[] nums, int s, int mid, int e) {
91+
int n = e - s + 1;
92+
int[] help = new int[n];
93+
int i = s, j = mid + 1, idx = 0;
94+
while (i <= mid && j <= e) {
95+
if (nums[i] > nums[j]) {
96+
res += (mid - i + 1);
97+
help[idx++] = nums[j++];
98+
} else {
99+
help[idx++] = nums[i++];
100+
}
101+
}
102+
while (i <= mid) {
103+
help[idx++] = nums[i++];
104+
}
105+
while (j <= e) {
106+
help[idx++] = nums[j++];
107+
}
108+
for (int t = 0; t < n; ++t) {
109+
nums[s + t] = help[t];
110+
}
111+
}
112+
}
113+
```
114+
115+
### ...
116+
```
117+
118+
```

‎lcof/面试题51. 数组中的逆序对/Solution.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
class Solution {
2+
private int res = 0;
3+
public int reversePairs(int[] nums) {
4+
int n = nums.length;
5+
if (n < 2) {
6+
return 0;
7+
}
8+
mergeSort(nums, 0, n - 1);
9+
return res;
10+
}
11+
12+
private void mergeSort(int[] nums, int s, int e) {
13+
if (s == e) {
14+
return;
15+
}
16+
int mid = s + ((e - s) >> 1);
17+
mergeSort(nums, s, mid);
18+
mergeSort(nums, mid + 1, e);
19+
merge(nums, s, mid, e);
20+
}
21+
22+
private void merge(int[] nums, int s, int mid, int e) {
23+
int n = e - s + 1;
24+
int[] help = new int[n];
25+
int i = s, j = mid + 1, idx = 0;
26+
while (i <= mid && j <= e) {
27+
if (nums[i] > nums[j]) {
28+
res += (mid - i + 1);
29+
help[idx++] = nums[j++];
30+
} else {
31+
help[idx++] = nums[i++];
32+
}
33+
}
34+
while (i <= mid) {
35+
help[idx++] = nums[i++];
36+
}
37+
while (j <= e) {
38+
help[idx++] = nums[j++];
39+
}
40+
for (int t = 0; t < n; ++t) {
41+
nums[s + t] = help[t];
42+
}
43+
}
44+
}

‎lcof/面试题51. 数组中的逆序对/Solution.py‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
class Solution:
2+
def reversePairs(self, nums: List[int]) -> int:
3+
self.res = 0
4+
5+
def merge(part1, part2, nums):
6+
len1, len2 = len(part1) - 1, len(part2) - 1
7+
t = len(nums) - 1
8+
while len1 >= 0 and len2 >= 0:
9+
if part1[len1] > part2[len2]:
10+
self.res += (len2 + 1)
11+
nums[t] = part1[len1]
12+
len1 -= 1
13+
else:
14+
nums[t] = part2[len2]
15+
len2 -= 1
16+
t -= 1
17+
while len1 >= 0:
18+
nums[t] = part1[len1]
19+
t -= 1
20+
len1 -= 1
21+
while len2 >= 0:
22+
nums[t] = part2[len2]
23+
t -= 1
24+
len2 -= 1
25+
26+
def merge_sort(nums):
27+
if len(nums) < 2:
28+
return
29+
mid = len(nums) // 2
30+
s1, s2 = nums[:mid], nums[mid:]
31+
merge_sort(s1)
32+
merge_sort(s2)
33+
merge(s1, s2, nums)
34+
35+
merge_sort(nums)
36+
return self.res

0 commit comments

Comments
 (0)