FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/code/lc493.java at master · mJackie/leetcode · GitHub
mJackie
/
leetcode
Public
Notifications
You must be signed in to change notification settings
Fork
135
Star
405
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
code
/
lc493.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
82 lines (73 loc) · 2.18 KB
Breadcrumbs
leetcode
/
code
/
lc493.java
Copy path
File metadata and controls
82 lines (73 loc) · 2.18 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package
code
;
import
java
.
util
.
Arrays
;
/*
* 493. Reverse Pairs
* 题意：逆序对
* 难度：Hard
* 分类：Binary Search, Divide and Conquer, Sort, Binary Indexed Tree, Segment Tree
* 思路：归并排序的思路 或者 树相关的数据结构
* 排序前先count
* 负数怎么解决？ 不用考虑，因为排序前先count
* Tips：lc315
*/
public
class
lc493
{
public
static
void
main
(
String
[]
args
) {
reversePairs
(
new
int
[]{
1
,
3
,
2
,
3
,
1
});
System
.
out
.
println
(
res
);
}
static
int
res
=
0
;
public
static
int
reversePairs
(
int
[]
nums
) {
mergeSort
(
nums
,
0
,
nums
.
length
-
1
);
return
res
;
}
public
static
void
mergeSort
(
int
[]
nums
,
int
left
,
int
right
){
if
(
left
<
right
){
int
mid
= (
left
+
right
)/
2
;
mergeSort
(
nums
,
left
,
mid
);
mergeSort
(
nums
,
mid
+
1
,
right
);
merge
(
nums
,
left
,
mid
,
right
);
}
}
public
static
void
merge
(
int
[]
nums
,
int
left
,
int
mid
,
int
right
){
//count elements
int
pos1
=
left
;
int
pos2
=
mid
+
1
;
int
count
=
0
;
while
(
pos1
<=
mid
){
//双指针 统计逆序对
if
(
pos2
>
right
||
nums
[
pos1
]<=(
double
)
nums
[
pos2
]*
2
) {
pos1
++;
res
+=
count
;
}
else
{
pos2
++;
count
++;
}
}
Arrays
.
sort
(
nums
,
left
,
right
+
1
);
// int[] nums_copy = nums.clone(); //耗时，大样例过不了
// pos1 = left; //注意pos1, pos2重新赋值
// pos2 = mid+1;
// int cur = left;
// while( pos1<=mid && pos2<=right ){
// if(nums_copy[pos1]<=nums_copy[pos2]){
// nums[cur] = nums_copy[pos1];
// pos1++;
// cur++;
// } else {
// nums[cur] = nums_copy[pos2];
// pos2++;
// cur++;
// }
// }
// while(pos1<=mid){
// nums[cur] = nums_copy[pos1];
// cur++;
// pos1++;
// }
// while(pos2<=right){
// nums[cur] = nums_copy[pos2];
// cur++;
// pos2++;
// }
}
}
Back
|
FazBrowse Home
|
New Git URL