题目

给定任意长度由 R、G、B 三种字符组成的随机字符串，在不增加空间复杂度的情况下按照 RRRGGGBBB 的方式排序。

1. 思路

定义三个变量 i、j、k。

• i 从左向右移动，指向第一个不是 R 的位置。
• j 从右向左移动，指向第一个不是 B 的位置。
• k 从左向右移动，若 k 指向的值是 R 则与 i 指向的值交换，i 右移；若 k 指向的值是 B 则与 j 指向的值交换，j 左移；若 k 指向的值是 G 则 k 直接右移。

2. 题解

2.1 Java 版

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));
}

执行结果：

排序前：RGBBGRGRBGGGRRGBBRRGG
排序后：RRRRRRRGGGGGGGGGBBBBB

2.2 Go 版

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,""))
}

执行结果：

排序前： RGBBGRGRBGGGRRGBBRRGG
排序后： RRRRRRRGGGGGGGGGBBBBB

2.3 Node 版

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(""))

执行结果：

排序前：RGBBGRGRBGGGRRGBBRRGG
排序后：RRRRRRRGGGGGGGGGBBBBB

2.4 Python 版

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)}")

执行结果：

排序前：RGBBGRGRBGGGRRGBBRRGG
排序后：RRRRRRRGGGGGGGGGBBBBB

2.5 Groovy 版

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)}")

执行结果：

排序前: RGBBGRGRBGGGRRGBBRRGG
排序后: RRRRRRRGGGGGGGGGBBBBB

版权所有

版权归属：Mayee

许可证：署名 4.0 国际 (CC-BY-4.0)