Skip to content

Commit bf007d3

Browse files
yanglbmeyanglbme
committed
feat: add golang solution to lcof problem: No.51. Reverse Pairs
1 parent cac2fba commit bf007d3

File tree

8 files changed

+134
-60
lines changed

8 files changed

+134
-60
lines changed

‎basic/sorting/QuickSort/Main.java‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -14,11 +14,11 @@ public static void main(String[] args) {
1414
}
1515
}
1616

17-
public static void quickSort(int[] nums, int left, int high) {
18-
if (left >= high) {
17+
public static void quickSort(int[] nums, int left, int right) {
18+
if (left >= right) {
1919
return;
2020
}
21-
int i = left - 1, j = high + 1;
21+
int i = left - 1, j = right + 1;
2222
int x = nums[left];
2323
while (i < j) {
2424
while (nums[++i] < x);
@@ -30,6 +30,6 @@ public static void quickSort(int[] nums, int left, int high) {
3030
}
3131
}
3232
quickSort(nums, left, j);
33-
quickSort(nums, j + 1, high);
33+
quickSort(nums, j + 1, right);
3434
}
3535
}

‎basic/sorting/QuickSort/Main.js‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -9,14 +9,14 @@ let getInputArgs = line => {
99
return line.split(' ').filter(s => s !== '').map(x => parseInt(x));
1010
}
1111

12-
function quickSort(nums, left, high) {
13-
if (left >= high) {
12+
function quickSort(nums, left, right) {
13+
if (left >= right) {
1414
return;
1515
}
1616

1717
let i = left - 1;
18-
let j = high + 1;
19-
let x = nums[(left + high) >> 1];
18+
let j = right + 1;
19+
let x = nums[(left + right) >> 1];
2020
while (i < j) {
2121
while (nums[++i] < x);
2222
while (nums[--j] > x);
@@ -27,7 +27,7 @@ function quickSort(nums, left, high) {
2727
}
2828
}
2929
quickSort(nums, left, j);
30-
quickSort(nums, j + 1, high);
30+
quickSort(nums, j + 1, right);
3131
}
3232

3333

‎basic/sorting/QuickSort/Main.py‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2,11 +2,11 @@
22
nums = list(map(int, input().split()))
33

44

5-
def quick_sort(nums, left, high):
6-
if left >= high:
5+
def quick_sort(nums, left, right):
6+
if left >= right:
77
return
8-
i, j = left - 1, high + 1
9-
x = nums[(left + high) >> 1]
8+
i, j = left - 1, right + 1
9+
x = nums[(left + right) >> 1]
1010
while i < j:
1111
while 1:
1212
i += 1
@@ -19,7 +19,7 @@ def quick_sort(nums, left, high):
1919
if i < j:
2020
nums[i], nums[j] = nums[j], nums[i]
2121
quick_sort(nums, left, j)
22-
quick_sort(nums, j + 1, high)
22+
quick_sort(nums, j + 1, right)
2323

2424

2525
quick_sort(nums, 0, N - 1)

‎basic/sorting/QuickSort/README.md‎

Lines changed: 23 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -5,11 +5,11 @@
55
**快速排序算法模板：**
66

77
```java
8-
void quickSort(int[] nums, int left, int high) {
9-
if (left >= high) {
8+
void quickSort(int[] nums, int left, int right) {
9+
if (left >= right) {
1010
return;
1111
}
12-
int i = left - 1, j = high + 1;
12+
int i = left - 1, j = right + 1;
1313
int x = nums[left];
1414
while (i < j) {
1515
while (nums[++i] < x);
@@ -21,7 +21,7 @@ void quickSort(int[] nums, int left, int high) {
2121
}
2222
}
2323
quickSort(nums, left, j);
24-
quickSort(nums, j + 1, high);
24+
quickSort(nums, j + 1, right);
2525
}
2626
```
2727

@@ -72,11 +72,11 @@ N = int(input())
7272
nums = list(map(int, input().split()))
7373

7474

75-
def quick_sort(nums, left, high):
76-
if left >= high:
75+
def quick_sort(nums, left, right):
76+
if left >= right:
7777
return
78-
i, j = left - 1, high + 1
79-
x = nums[(left + high) >> 1]
78+
i, j = left - 1, right + 1
79+
x = nums[(left + right) >> 1]
8080
while i < j:
8181
while 1:
8282
i += 1
@@ -89,7 +89,7 @@ def quick_sort(nums, left, high):
8989
if i < j:
9090
nums[i], nums[j] = nums[j], nums[i]
9191
quick_sort(nums, left, j)
92-
quick_sort(nums, j + 1, high)
92+
quick_sort(nums, j + 1, right)
9393

9494

9595
quick_sort(nums, 0, N - 1)
@@ -115,11 +115,11 @@ public class Main {
115115
}
116116
}
117117

118-
public static void quickSort(int[] nums, int left, int high) {
119-
if (left >= high) {
118+
public static void quickSort(int[] nums, int left, int right) {
119+
if (left >= right) {
120120
return;
121121
}
122-
int i = left - 1, j = high + 1;
122+
int i = left - 1, j = right + 1;
123123
int x = nums[left];
124124
while (i < j) {
125125
while (nums[++i] < x);
@@ -131,7 +131,7 @@ public class Main {
131131
}
132132
}
133133
quickSort(nums, left, j);
134-
quickSort(nums, j + 1, high);
134+
quickSort(nums, j + 1, right);
135135
}
136136
}
137137
```
@@ -150,14 +150,14 @@ let getInputArgs = line => {
150150
return line.split(' ').filter(s => s !== '').map(x => parseInt(x));
151151
}
152152

153-
function quickSort(nums, left, high) {
154-
if (left >= high) {
153+
function quickSort(nums, left, right) {
154+
if (left >= right) {
155155
return;
156156
}
157157

158158
let i = left - 1;
159-
let j = high + 1;
160-
let x = nums[(left + high) >> 1];
159+
let j = right + 1;
160+
let x = nums[(left + right) >> 1];
161161
while (i < j) {
162162
while (nums[++i] < x);
163163
while (nums[--j] > x);
@@ -168,7 +168,7 @@ function quickSort(nums, left, high) {
168168
}
169169
}
170170
quickSort(nums, left, j);
171-
quickSort(nums, j + 1, high);
171+
quickSort(nums, j + 1, right);
172172
}
173173

174174

@@ -192,12 +192,12 @@ package main
192192

193193
import "fmt"
194194

195-
func quickSort(nums []int, left, high int) {
196-
if left >= high {
195+
func quickSort(nums []int, left, right int) {
196+
if left >= right {
197197
return
198198
}
199-
i, j := left-1, high+1
200-
x := nums[(left+high)>>1]
199+
i, j := left-1, right+1
200+
x := nums[(left+right)>>1]
201201
for i < j {
202202
for {
203203
i++
@@ -216,7 +216,7 @@ func quickSort(nums []int, left, high int) {
216216
}
217217
}
218218
quickSort(nums, left, j)
219-
quickSort(nums, j+1, high)
219+
quickSort(nums, j+1, right)
220220
}
221221

222222
func main() {

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

Lines changed: 49 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -37,25 +37,24 @@ class Solution:
3737
return 0
3838
mid = (left + right) >> 1
3939
res = merge_sort(nums, left, mid) + merge_sort(nums, mid + 1, right)
40-
i, j, k = left, mid + 1, 0
40+
i, j = left, mid + 1
4141
tmp = []
4242
while i <= mid and j <= right:
4343
if nums[i] <= nums[j]:
4444
tmp.append(nums[i])
4545
i += 1
4646
else:
47+
res += (mid - i + 1)
4748
tmp.append(nums[j])
4849
j += 1
49-
res += (mid - i + 1)
5050
while i <= mid:
5151
tmp.append(nums[i])
5252
i += 1
5353
while j <= right:
5454
tmp.append(nums[j])
5555
j += 1
5656
for i in range(left, right + 1):
57-
nums[i] = tmp[k]
58-
k += 1
57+
nums[i] = tmp[i - left]
5958
return res
6059

6160
return merge_sort(nums, 0, len(nums) - 1)
@@ -67,8 +66,8 @@ class Solution:
6766

6867
```java
6968
class Solution {
70-
private static int[] tmp = new int[50000];
71-
69+
private static int[] tmp = new int[50010];
70+
7271
public int reversePairs(int[] nums) {
7372
return mergeSort(nums, 0, nums.length - 1);
7473
}
@@ -77,15 +76,15 @@ class Solution {
7776
if (left >= right) {
7877
return 0;
7978
}
80-
int mid = (left + right) >>> 1;
79+
int mid = (left + right) >> 1;
8180
int res = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
8281
int i = left, j = mid + 1, k = 0;
8382
while (i <= mid && j <= right) {
8483
if (nums[i] <= nums[j]) {
8584
tmp[k++] = nums[i++];
8685
} else {
87-
tmp[k++] = nums[j++];
8886
res += (mid - i + 1);
87+
tmp[k++] = nums[j++];
8988
}
9089
}
9190
while (i <= mid) {
@@ -94,8 +93,8 @@ class Solution {
9493
while (j <= right) {
9594
tmp[k++] = nums[j++];
9695
}
97-
for (i = left, j = 0; i <= right; ++i) {
98-
nums[i] = tmp[j++];
96+
for (i = left; i <= right; ++i) {
97+
nums[i] = tmp[i - left];
9998
}
10099
return res;
101100
}
@@ -222,6 +221,46 @@ function reversePairs(nums: number[]): number {
222221
};
223222
```
224223

224+
### **Go**
225+
226+
```go
227+
func reversePairs(nums []int) int {
228+
return mergeSort(nums, 0, len(nums)-1)
229+
}
230+
231+
func mergeSort(nums []int, left, right int) int {
232+
if left >= right {
233+
return 0
234+
}
235+
mid := (left + right) >> 1
236+
res := mergeSort(nums, left, mid) + mergeSort(nums, mid+1, right)
237+
i, j := left, mid+1
238+
var tmp []int
239+
for i <= mid && j <= right {
240+
if nums[i] <= nums[j] {
241+
tmp = append(tmp, nums[i])
242+
i++
243+
} else {
244+
res += (mid - i + 1)
245+
tmp = append(tmp, nums[j])
246+
j++
247+
}
248+
}
249+
for i <= mid {
250+
tmp = append(tmp, nums[i])
251+
i++
252+
}
253+
for j <= right {
254+
tmp = append(tmp, nums[j])
255+
j++
256+
}
257+
for i = left; i <= right; i++ {
258+
nums[i] = tmp[i-left]
259+
}
260+
return res
261+
}
262+
```
263+
225264
### **...**
226265

227266
```

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

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
func reversePairs(nums []int) int {
2+
return mergeSort(nums, 0, len(nums)-1)
3+
}
4+
5+
func mergeSort(nums []int, left, right int) int {
6+
if left >= right {
7+
return 0
8+
}
9+
mid := (left + right) >> 1
10+
res := mergeSort(nums, left, mid) + mergeSort(nums, mid+1, right)
11+
i, j := left, mid+1
12+
var tmp []int
13+
for i <= mid && j <= right {
14+
if nums[i] <= nums[j] {
15+
tmp = append(tmp, nums[i])
16+
i++
17+
} else {
18+
res += (mid - i + 1)
19+
tmp = append(tmp, nums[j])
20+
j++
21+
}
22+
}
23+
for i <= mid {
24+
tmp = append(tmp, nums[i])
25+
i++
26+
}
27+
for j <= right {
28+
tmp = append(tmp, nums[j])
29+
j++
30+
}
31+
for i = left; i <= right; i++ {
32+
nums[i] = tmp[i-left]
33+
}
34+
return res
35+
}

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

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
class Solution {
2-
private static int[] tmp = new int[50000];
3-
2+
private static int[] tmp = new int[50010];
3+
44
public int reversePairs(int[] nums) {
55
return mergeSort(nums, 0, nums.length - 1);
66
}
@@ -9,15 +9,15 @@ private int mergeSort(int[] nums, int left, int right) {
99
if (left >= right) {
1010
return 0;
1111
}
12-
int mid = (left + right) >>> 1;
12+
int mid = (left + right) >> 1;
1313
int res = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
1414
int i = left, j = mid + 1, k = 0;
1515
while (i <= mid && j <= right) {
1616
if (nums[i] <= nums[j]) {
1717
tmp[k++] = nums[i++];
1818
} else {
19-
tmp[k++] = nums[j++];
2019
res += (mid - i + 1);
20+
tmp[k++] = nums[j++];
2121
}
2222
}
2323
while (i <= mid) {
@@ -26,8 +26,8 @@ private int mergeSort(int[] nums, int left, int right) {
2626
while (j <= right) {
2727
tmp[k++] = nums[j++];
2828
}
29-
for (i = left, j = 0; i <= right; ++i) {
30-
nums[i] = tmp[j++];
29+
for (i = left; i <= right; ++i) {
30+
nums[i] = tmp[i - left];
3131
}
3232
return res;
3333
}

0 commit comments

Comments
 (0)