0

该函数接受一个代表鹅卵石的字符数组并将该数组重新排列为红色、白色和蓝色字符。还返回重新排列时进行的交换次数。如果输入合法并且重新排列成功，则该函数返回 1。如果在输入中发现非法字符，则返回 0。

boolean processInput(char *pebbles, int *noOfSwaps){

    int low;
    int mid;
    int high;

    *noOfSwaps = 0;

    low = 0;

    while (low < strlen(pebbles) && color(*(pebbles + low)) == RED)
            low++;

    high = strlen(pebbles) - 1;

    while (high >= 0 && color(*(pebbles + high)) == BLUE)
            high--;

    mid = low;

    while (mid <= high){

            if (color(*(pebbles + mid)) == RED){

                    if (mid == low){

                            low++;
                            mid++;
                    }

                    else{

                            swap((pebbles + mid), (pebbles + low));

                            (*noOfSwaps)++;
                            low++;
                            mid++;
                    }
            }

            else if (color(*(pebbles + mid)) == WHITE)
                    mid++;

            else if (color(*(pebbles + mid)) == BLUE){
                    if (color(*(pebbles + high)) == BLUE)
                            high--;

                    else{
                            swap((pebbles + mid), (pebbles + high));
                            (*noOfSwaps)++;
                            high--;
                    }
            }      
            else
                    return 0;
    }
    return 1;
}

^^^ 上面是我的代码。只有一个功能。需要知道该功能的最坏情况复杂性和原因。谢谢！

4

1 回答 1

1

O(n) + O(color())当所有的鹅卵石都是红色时，这条线将导致最小值。如果颜色是O(1)（它可能是），那么它只是O(n)：

while (low < strlen(pebbles) && color(pebbles[low]) == RED)
    low++;

其余代码似乎只检查每个元素的颜色一次，因此O(n) + O(color())也是如此。

所以我要去O(n)。

编辑：从头开始，他strlen在那个while循环中调用。我要把这个升级到O(n^2). n的长度在哪里pebbles。让这回到O(n). 调用strlen()一次，并缓存该值。

于 2013-03-10T02:43:06.867 回答