FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
JavaArithmetic/src/LeetCode/Leetcode75.java at master · git-jhy/JavaArithmetic · GitHub
git-jhy
JavaArithmetic
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
JavaArithmetic
/
src
/
LeetCode
/
Leetcode75.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
57 lines (51 loc) · 1.45 KB
Breadcrumbs
JavaArithmetic
/
src
/
LeetCode
/
Leetcode75.java
Copy path
File metadata and controls
57 lines (51 loc) · 1.45 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
package
LeetCode
;
//https://leetcode.com/problems/sort-colors/description/
public
class
Leetcode75
{
/**
* 扫描出现的频率，然后根据频率再填充回去
*
* @param nums
*/
// 时间复杂度: O(n)
// 空间复杂度: O(1)
public
void
sortColors
(
int
[]
nums
) {
int
[]
count
= {
0
,
0
,
0
};
// 存放0, 1, 2三个元素的频率
for
(
int
i
=
0
;
i
<
nums
.
length
;
i
++) {
assert
nums
[
i
] >=
0
&&
nums
[
i
] <=
2
;
count
[
nums
[
i
]]++;
}
int
index
=
0
;
for
(
int
i
=
0
;
i
<
count
[
0
];
i
++)
nums
[
index
++] =
0
;
for
(
int
i
=
0
;
i
<
count
[
1
];
i
++)
nums
[
index
++] =
1
;
for
(
int
i
=
0
;
i
<
count
[
2
];
i
++)
nums
[
index
++] =
2
;
}
/**
* 三路快排思路
*
* @param nums
*/
// 时间复杂度: O(n)
// 空间复杂度: O(1)
public
void
sortColors2
(
int
[]
nums
) {
int
zero
= -
1
;
// [0...zero] == 0
int
two
=
nums
.
length
;
// [two...n-1] == 2
for
(
int
i
=
0
;
i
<
two
; ) {
if
(
nums
[
i
] ==
1
)
i
++;
else
if
(
nums
[
i
] ==
2
)
swap
(
nums
,
i
, --
two
);
else
{
// nums[i] == 0
assert
nums
[
i
] ==
0
;
swap
(
nums
, ++
zero
,
i
++);
}
}
}
private
void
swap
(
int
[]
nums
,
int
i
,
int
j
) {
int
t
=
nums
[
i
];
nums
[
i
] =
nums
[
j
];
nums
[
j
] =
t
;
}
}
Back
|
FazBrowse Home
|
New Git URL