0

有 n 长度的 char 数组。数组只能包含任何顺序 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 );
         }
     }
    }
4

4 回答 4

4

我不确定这个问题是否在 SO 的范围内，但我将提出一个替代解决方案，主要是因为我发现任务规范很烦人。不需要实际的“排序”。:)

public static void sort(char[] arr) {
    int r = 0, b = 0, w = 0;
    for(int i = 0; i < arr.length; i++) {
        if(arr[i] == 'R') r++;
        else if(arr[i] == 'B') b++;
        else w++;
    }
    int o = 0;
    for(; r > 0; r--) arr[o++] = 'R';
    for(; b > 0; b--) arr[o++] = 'B';
    for(; w > 0; w--) arr[o++] = 'W';
}
于 2013-09-28T15:46:23.217 回答
1

使用交换试试这个：

public static void main(String[] args) {
    char[] arr = "WBRBBWBRRBWBR".toCharArray();
    sort(arr);
    System.out.println(String.valueOf(arr));
}
public static void sort(char[] arr) {
    int rCount = sortFirst(arr, 0, 'R');
    sortFirst(arr, rCount, 'B');
}
public static int sortFirst(char[] arr, int offset, char ch) {
    int chCount = 0;
    for (int i = offset; i < arr.length; i++) {
        if (arr[i] == ch) {
            if (i > offset + chCount)
                swap(arr, offset + chCount, i);
            chCount++;
        }
    }
    return chCount;
}
public static void swap(char[] arr, int index1, int index2) {
    char h = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = h;
}
于 2013-09-28T16:16:01.747 回答
0

Never mind, here is improved version of my above algorithm. It has one less swap call and uses switches rather than if else block

public static void sort(char[] arr){
     int rIndex = 0, wIndex = arr.length -1;
     for (int i = 0 ; i <= wIndex;){
        switch(arr[i]){
          case 'R':
            swap(arr, i, rIndex ++ );
            i ++;
            break;
          case 'W':
            swap(arr, i, wIndex -- );
            break;
          case 'B':
            i ++;
            break;
          default: 
             throw new IllegalArguementException(arr[i] + " is not allowed in the array");

       }
   }
}
于 2013-09-28T19:05:46.617 回答
0

最快的排序可能是QuickSort，它的时间效率是O(n log n)平均和最坏的情况O(n*n)。最好O(n)的情况是它已经排序......

获得你想要的效率是不可能的。您首先要做的是创建一个比较 2 个字符的方法并在那里执行您的算法。然后制作一种交换字符的方法。

如果您想达到这种效率，您不必对它们进行排序。你必须像@Dolda2000 那样计算它们并按照你想要的顺序构建一个字符数组。你不能比排序更快QuickSort

于 2013-09-28T19:19:18.493 回答