<分区>
有一个长度为n的字符数组。数组只能包含任何顺序为 R、B、W 的元素。
您需要对数组进行排序,以便顺序应为 R、B、W,即所有 R 将首先出现,然后是 B,然后是 W。
约束条件:时间复杂度为O(n),空间复杂度为O(1)。
假设:您可以假设一个交换方法带有签名 swap(char[] arr, int index1, int index2)
在单位时间内交换数字。
实现方法: public sort(char[]array);
这是我的实现。感谢任何人提供更好的解决方案。如果有任何错误,任何人都可以自由地指出我。
public static void sort(char[] arr){
int rIndex = 0, wIndex = arr.length -1;
for (int i = 0 ; i <= wIndex; i ++ ){
if ( arr[i] == 'R' ){
swap(arr, i , rIndex ++ );
} else if (arr[i] == 'W' ){
swap(arr, i , wIndex -- );
}else if ( arr[i] == 'B' ){
swap(arr, i , rIndex );
}
}
}