题目
给定任意长度由 R、G、B 三种字符组成的随机字符串，在不增加空间复杂度的情况下按照 RRRGGGBBB 的方式排序
思路
定义三个变量 i、j、k。
- i 从左向右移动，指向第一个不是 R 的位置。
- j 从右向左移动，指向第一个不是 B 的位置。
- k 从左向右移动，若 k 指向的值是 R 则与 i 指向的值交换，i 右移；若 k 指向的值是 B 则与 j 指向的值交换，j 左移；若 k 指向的值是 G 则 k 直接右移。
题解
Java 版
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
| public static void main(String[] args) {
String[] arr = "RGBBGRGRBGGGRRGBBRRGG".split("");
System.out.println("排序前：" + String.join("", arr));
for (int i = 0, k = 0, j = arr.length - 1; k <= j; ) {
if ("R".equals(arr[i])) {
i++;
if (k < i) {
k = i;
}
continue;
}
if ("B".equals(arr[j])) {
j--;
continue;
}
if ("R".equals(arr[k])) {
arr[k] = arr[i];
arr[i++] = "R";
} else if ("G".equals(arr[k])) {
k++;
} else if ("B".equals(arr[k])) {
arr[k] = arr[j];
arr[j--] = "B";
}
}
System.out.println("排序后：" + String.join("", arr));
}
|
执行结果：
1
2
| 排序前：RGBBGRGRBGGGRRGBBRRGG
排序后：RRRRRRRGGGGGGGGGBBBBB
|
Go 版
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
| func main() {
slice := strings.Split("RGBBGRGRBGGGRRGBBRRGG", "")
fmt.Println("排序前：",strings.Join(slice,""))
for i, k, j := 0, 0, len(slice)-1; k <= j; {
if slice[i] == "R" {
i++
if k < i {
k = i
}
continue
}
if slice[j] == "B" {
j--
continue
}
if slice[k] == "R" {
slice[k] = slice[i]
slice[i] = "R"
i++
} else if slice[k] == "G" {
k++
} else if slice[k] == "B" {
slice[k] = slice[j]
slice[j] = "B"
j--
}
}
fmt.Println("排序后：",strings.Join(slice,""))
}
|
执行结果：
1
2
| 排序前： RGBBGRGRBGGGRRGBBRRGG
排序后： RRRRRRRGGGGGGGGGBBBBB
|
Node 版
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
| let arr = 'RGBBGRGRBGGGRRGBBRRGG'.split('')
console.log('排序前：' + arr.join(""))
for (let i = 0, k = 0, j = arr.length - 1; k <= j;) {
if (arr[i] === 'R'){
i++
if (k < i){
k = i
}
continue
}
if (arr[j] === 'B'){
j--
continue
}
if (arr[k] === 'R'){
arr[k] = arr[i]
arr[i] = 'R'
i++
}else if (arr[k] === 'G'){
k++
}else if (arr[k] === 'B'){
arr[k] = arr[j]
arr[j] = 'B'
j--
}
}
console.log('排序后：' + arr.join(""))
|
执行结果：
1
2
| 排序前：RGBBGRGRBGGGRRGBBRRGG
排序后：RRRRRRRGGGGGGGGGBBBBB
|
Python 版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| arr = list('RGBBGRGRBGGGRRGBBRRGG')
print(f"排序前：{''.join(arr)}")
i, k, j = 0, 0, len(arr) - 1
while k <= j:
if arr[i] == 'R':
i += 1
if k < i:
k = i
continue
if arr[j] == 'B':
j -= 1
continue
if arr[k] == 'R':
arr[k] = arr[i]
arr[i] = 'R'
i += 1
elif arr[k] == 'G':
k += 1
elif arr[k] == 'B':
arr[k] = arr[j]
arr[j] = 'B'
j -= 1
print(f"排序后：{''.join(arr)}")
|
执行结果：
1
2
| 排序前：RGBBGRGRBGGGRRGBBRRGG
排序后：RRRRRRRGGGGGGGGGBBBBB
|
Groovy 版
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
| def arr = 'RGBBGRGRBGGGRRGBBRRGG'.split("")
println("排序前: ${String.join("",arr)}")
for (def i = 0, k = 0, j = arr.length - 1; k <= j;) {
if (arr[i] == 'R') {
i++
if (k < i) {
k = i
}
continue
}
if (arr[j] == 'B') {
j--
continue
}
if (arr[k] == 'R') {
arr[k] = arr[i]
arr[i++] = 'R'
} else if (arr[k] == 'G') {
k++
} else if (arr[k] == 'B') {
arr[k] = arr[j]
arr[j--] = 'B'
}
}
println("排序后: ${String.join("",arr)}")
|
执行结果：
1
2
| 排序前: RGBBGRGRBGGGRRGBBRRGG
排序后: RRRRRRRGGGGGGGGGBBBBB
|
